LeetCode Array Part 2 (977, 209)

Leetcode No.977 Squares of a Sorted Array

Question Description :
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Original Page

In certain circumstances, both positive numbers and negative numbers in the original array so it might be hard for us to conduct this problem in-place!
-> need a new array with the same shape

Method 1

1. First, we can compare the data of the second last element in the new array with the squared element in the original array

2. Then based on the result of the comparison, we can fill in the element to the new array to ensure a non-ascending order from (current index)right to left (beginning) which means the entire new array will be still a non-descending order.

Then according to their

        nums[0] = nums[0]*nums[0];
        if(nums.length == 1){
            return nums;
        }

        int[] output = new int[nums.length];
        output[0] = nums[0];

        for(int i=1; i<nums.length; i++){
            int j = i;
            int num = nums[i]*nums[i];
            boolean isFinish = false;
            // quit condition, if we swap all element or has filled in the right place
            while(!isFinish && j>0){
                // filled in the right place
                if(output[j-1]<=num){
                    output[j] = num;
                    isFinish = true;
                }
                // now we have to move the larger element to the right until find the right place
                else{
                    output[j] = output[j-1];                    
                    output[j-1] = num;
                    j--;
                }
            }
        }
        return output;
    }

The order of this Method is O(n^2)，somewhat suboptimal.
But this method will still work when the original array is not sorted!

Method 2

double vector

• The sorted non-decreasing original array, which implies that the absolute value of the left side and right side might be larger when both positive and negative numbers exist.
• And when only positive or negative numbers exist, it will impact not too much.
• We can compare the left element to the right element first (because it might be the biggest one in a sorted array)

        int[] output = new int[nums.length];

        // double vector
        int left = 0; int right = nums.length-1;

        //make it easy to process (original array is sorted )
        for(int i=nums.length-1; i>-1; i--){
            if(Math.abs(nums[left]) >Math.abs(nums[right])){
                output[i] = nums[left]*nums[left];
                left++;
            } else{
                output[i] = nums[right]*nums[right];
                right--;
            }
                }
    return output;
        }

The complexity now is O(n) improved a lot more than before O(n^2)!
But be careful the condition that now the original array is sorted we can use it in this way!

LeetCode No.209 Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray
whose sum is greater than or equal to the target. If there is no such subarray, return 0 instead.
A subarray is a contiguous non-empty sequence of elements within an array.
Question original page

keywords:
subarray, contiguous, sum

• each subarray will be from left index boundary i to right index boundary.
• then we change the boundary size
• in each inner loop we find the subarray, by changing j to adjust the right index boundary
• in each outer loop we find the subarray, by changing i to adjust the left index boundary.

        int cnt = Integer.MAX_VALUE; 
        for(int i=0; i<nums.length; i++){
            int sum = 0;
            for(int j=i; j<nums.length; j++){
                if(nums[j] >= target){
                    return 1;
                } 
                sum += nums[j];
                if(sum >= target){
                    cnt = Math.min(cnt, j-i+1);
                    break;
                }
            }
        }
        if (cnt == Integer.MAX_VALUE) {return 0;}

        return cnt;
    }

But it will cause Time Limit Exceeded in No.19 test cases.
because this method will be O(n^2) in complexity .

Method 2

Now we need to optimize the above algorithm.
First, we should identify the potential progression points above.

• we use a double loop and it might cause some redundant computation e.g. we always fixed an index boundary even though there are useless and effectless loops among it we can not jump out and we can only wait for the inner loop to finish normally.

So here we consider a new way, a dynamic way to conduct the loop inspired by the thought of double vector

    public int minSubArrayLen(int target, int[] nums) {
            int left = 0;
            int right = 0;
            int count = Integer.MAX_VALUE;
            int sum = 0;

            while(right<nums.length){
                sum += nums[right];

                while(sum >= target){
                    // now we should update left side because we have find subarray but it might not be the minimum one.            
                    count = Math.min(count, right-left+1);
                    // the left boundary do a unit right shift,we will decrease the original left boundary element.
                    sum -= nums[left++];

                } 
                right++;
            }
        return count==Integer.MAX_VALUE ? 0 : count;
    }

Here I will summarize I suffered the problem during my coding

• Condition

while(left<=right && right<nums.length && left<nums.length)

I used two more useless conditions to evaluate the loop it is redundant because in

• use if instead of while in the inner part wrong code here:

                if(sum >= target){
                    //Now we should update the left side because we have found subarray but it might not be the minimum one.            
                    count = Math.min(count, right-left+1);
                    // the left boundary does a unit right shift, we will decrease the original left boundary element.
                    sum -= nums[left++];

                } else{
                    sum += nums[right++];
                }
            }

if using if it will do a left-boundary-shift once so it will also loss some potential subarray!

• Activate loop too early. Before I usesum += nums[right++];` which is a wrong example!

This will change the inner part code right away so that it can cause a wrong answer because it modifies left before doing the evaluation.
** Be careful about the condition!**