1.ProductExceptSelf 2.MaximumSubarray

ProductExceptSelf

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].

You must write an algorithm that runs in O(n) time and without using the division operation.

Example

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Approach 1:

Without reading the question carefully enough, I thought I found a clever way with only 1 iteration along the list, which was have a product of all the values and simply divide the ith value on the output list.

However, without the use of division, I was stuck on how to solve this question.

Looking at the solution, I figured out that I should look at the product of array except self as a product of left part and the right part of the element in the array. That way, I could iterate through the list twice to keep track of all the left-side products and the right-side products, and ultimately multiply them all together while iterating.

1. Iterate from the left to the right to keep track of all the ‘left-side’ products
2. Iterate from the right to the left to keep track of all the ‘right-side’products
3. While iterating from the right, multiply it with the left-side products to ultimately get the answer

Implementation:

class Solution:
    

    def productExceptSelf(self, nums):
        m = len(nums)
        result = [1]* m
        for i in range(1,m):
            result[i] = nums[i-1] * result[i-1]
        R = 1
        for i in reversed(range(m)):
            result[i] *= r
            r *= nums[i]
        
        return result

Complexity Analysis:

Time Complexity:O(n) where n is the length of the list

Space Complexity: O(1)

MaximumSubarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

Approach 1:

First, I thought this problem would be easy that I would only have to add positive numbers to maximize the sums. Naively, I thought that I could cut my subarrays as soon as a negative number appears. Sadly, this was not the case since that a relatively small negative number (for example -1) can follow a big positive number(10).

Therefore, I thought that I could iterate the list inspecting for all the sums that each addition of elements in the nums could give me, accounting for the fact that the addition of the new element would be actually higher than just the new number itself.

Implementation:

class Solution:
    

    def maxSubArray(self, nums):
        m = len(nums)
        result = [0] * m
        for i in range(m):
            result[i] = result[i-1] + nums[i] if result[i-1] + nums[i] > nums[i] else nums[i]
        
        return max(profit)
        

Complexity Analysis:

Time Complexity:O(n) where n is the length of the list nums since we are iterating through the list once, and also using a max function which is a O(n) operation.

Space Complexity: O(n)

Approach 2:

Looking at this question as inspecting for which values are worth keeping in the addtion of the maximum sum, I noticed that all the positive values are actually okay to keep. It is the negative values that we only need to think whether to keep or not.

While my first approach was efficient in terms of time, it was not super efficient since it makes use of another list.

Inspired from Kardane’s Algorithm, whenever the sum of the array is negative, we know the entire array is not worth keeping. We can actually keep track of that by having an integer variable ‘current_subarray’ and add values of each element there. Whenever it becomes negative, reset it to 0 and move on to the next element.

1. Initialize 2 integer variables and set both of the equal to the first value of the array.
2. Iterate through the array, starting with the 2nd element.
3. For each element, add it to current_subarray. If current_subarray becomes negative, we know it is not worth keeping so throw it away.
4. However, update maxSubarray everytime we find a new maximum of current_subarray.
5. return maxSubarray

Implementation:

class Solution:
    

    def maxSubArray(self, nums):
        m = len(nums)
        current_subarray, maxSubarray = nums[0], nums[0]
        for i in range(1,m):
            current_subarray = max(num, current_subarray + num)
            maxSubarray = max(current_subarray, maxSubarray)
        
        return maxSubarray
        

Complexity Analysis:

Time Complexity:O(n) where n is the length of the list nums

Space Complexity: O(1)

Reflection

It was intersting to see how to tackle these array questions. It was intellectually challenging and more importantly, kind of fun.