Majid Rezaei

One of the most fascinating concepts in computer science is algorithm analysis and optimization. Finding ways to enhance algorithm efficiency can significantly improve a project's quality. These improvements often involve reducing time or space complexity of critical functions. Optimization strategies may focus on redesigning the algorithm itself or implementing techniques such as caching. By refining algorithms, developers can create more efficient and scalable software solutions. Iv been fascinated by these concepts from the start of my programming journey. cases like fast_inverse_sqrt and a few similar ones just show how much creative a developer can be.
In this post, I aim to solve several problems and analyze them using mathematical concepts. I'm also attempting to develop an algorithm analysis component. However, this aspect has proven to be more challenging than i initially anticipated, and I'll need to dedicate more time to fully explore it.

Leetcode questions

Problem 1

Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.

So the idea is fairly basic, we want to see if there is a duplicate or more than dublicate (3, 4, etc) in a an array. there are multiple ways to solve this prolem but im going to analyse three different solutions.

                
                    function containsDuplicate(array $nums):bool
                    {
                        $n = count($nums);
                        for ($i = 0; $i < $n - 1; $i++) {
                            for ($j = $i + 1; $j < $n; $j++) {
                                if ($nums[$i] == $nums[$j]) {
                                    return true;
                                }
                            }
                        }
                        return false;
                    }

                
                    function containsDuplicate(array $nums):bool {
                        $hashset = [];
                        foreach ($nums as $num) {
                            if (isset($hashset[$num])) {
                                return true;
                            }
                            $hashset[$num] = true;
                        }
                        return false;
                    }

in this code the time complixity is of o(n) and compared to previous version is more effective. in this code using a hashset makes the process much seasier since we will be using more memory to save the entered array for comparison.

Problem 2

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j!= i and nums[j] < nums[i]. Return the answer in an array.

an easy question with the most obvious solution being comparing the items of the array to the rest. this function is of O(

n^{2}

)

                
                    function containsDuplicate(array $nums):bool {
                        $hashset = [];
                        foreach ($nums as $num) {
                            if (isset($hashset[$num])) {
                                return true;
                            }
                            $hashset[$num] = true;
                        }
                        return false;
                    }

function below efficiently counts how many numbers are smaller than each number in the input array. It uses a counting sort approach by first creating a frequency array of all numbers, then calculating a cumulative sum of frequencies. This cumulative sum at each index represents how many numbers are smaller than or equal to that index. Finally, it iterates through the original array, using the cumulative sum to determine how many numbers are smaller than each number. This method is more efficient than comparing each number to every other number, especially for larger arrays with a limited range of values. O(m+n)

            
                function smallerNumbersThanCurrent1($nums) {
                    $count = count($nums);
                    $max = max($nums);
                    
                    $frequency = array_fill(0, $max + 1, 0);
                    foreach ($nums as $num) {
                        $frequency[$num]++;
                    }
                    
                    for ($i = 1; $i <= $max; $i++) {
                        $frequency[$i] += $frequency[$i - 1];
                    }
                    
                    $result = [];
                    foreach ($nums as $num) {
                        if ($num == 0) {
                            $result[] = 0;
                        } else {
                            $result[] = $frequency[$num - 1];
                        }
                    }
                    
                    return $result;
                }

Problem 3

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation. complixity of this function is O(

n^{2}

)

        
            function arrayProduct1(array $array)
            {   
                $arrayproduct = [];
                $result = [];
                
                   foreach($array as $index => $number)
                {
                    $tempArray = $array;
                    unset($tempArray[$index]);
                    $arrayproduct[] = array_values($tempArray);
                    
                }
            foreach($arrayproduct as $product)
            {
                $result []=array_product($product);
            }
            return $result;
            }

time complixity of the code below of O(n)

        
            function arrayProduct2(array $nums) {
                $n = count($nums);
                $answer = array_fill(0, $n, 1);
                $prefix = 1;
                for ($i = 0; $i < $n; $i++) {
                    $answer[$i] *= $prefix;
                    $prefix *= $nums[$i];
                }
                    $suffix = 1;
                for ($i = $n - 1; $i >= 0; $i--) {
                    $answer[$i] *= $suffix;
                    $suffix *= $nums[$i];
                }
                return $answer;
            }