Chapter 5 - Arrays

Question 1

Rotate an array by k digits/steps

Answer 1

1. First reverse the entire array
2. Reverse first k numbers
3. Reverse remaining n-k numbers

Question 2

Median of two sorted arrays

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Answer 2

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        l1, l2 = len(nums1), len(nums2) 

    if l1>l2:
        nums1, nums2, l1, l2 = nums2, nums1, l2, l1

        if not nums1 and not nums2:
            return 0
        if nums1 and not nums2:
            mid = l1//2
            if l1 % 2 == 0:
                return (nums1[mid] + nums1[mid-1])/2
            else:
                return nums1[mid]

        if not nums1 and nums2:
            mid = l2//2
            if l2 % 2 == 0:
                return (nums2[mid] + nums2[mid-1])/2
            else:
                return nums2[mid]

    start, end = 0, l1

    while start <= end:

        partition_x = (start+end) // 2
        #partition_x + partition_y = (len(nums1) + len(nums2) + 1)/2
        partition_y =  (l1 + l2 + 1)//2 - partition_x

        max_left_x = float('-inf') if partition_x == 0 else nums1[partition_x-1]
        max_left_y = float('-inf') if partition_y == 0 else nums2[partition_y-1]

        min_right_x = float('inf') if partition_x == l1 else nums1[partition_x]
        min_right_y = float('inf') if partition_y == l2 else nums2[partition_y]

        if max_left_x <= min_right_y and max_left_y <= min_right_x:
            if (l1+l2)%2!=0:
                return max(max_left_x, max_left_y)
            else:
                min_right = min(min_right_x, min_right_y)
                max_left = max(max_left_x, max_left_y)
                return (min_right+max_left) / 2                

        elif max_left_x > min_right_y:
            end = partition_x - 1
        else:
            start = partition_x + 1

Question 3

Locate a small window to be sorted to sort the complete array

Answer 3

Idea: As we go forward, every value should be greater than the last value
Logic:
1. Traverse the array, check if a value is lesser than max value till this point, then this needs to be sorted.
Finally, the index for max value to be sorted
2. Reverse traverse the array in reverse, check if every element is lower than the next value, if not this needs to be sorted
Finally, find the index of min value to be sorted

max_i = 0
min_i = len(a)-1

max_ele = a[max_i]
min_ele = a[min_i]

for idx, ele in enumerate(a):
    if ele > max_ele:
        max_ele = ele
    elif ele < max_ele:
        max_i = idx

for idx, ele in enumerate(reversed(a)):
    if ele < min_ele:
        min_ele = ele
    elif ele > min_ele:
        min_i = idx

min_i = len(a) - min_i

Question 4

Product of array except for self

Answer 4

Idea:
Product at an index is a product of right values and left values to the current index
Logic:
1. Traverse the array, replace each element with product till the index before that
2. Reverse traverse the array, replace each element with product till the index before that
3. Final output array with value at each index as a product of values in both arrays at that index

def productExceptSelf(self, nums: List[int]) -> List[int]:
        prefix_arr = list()
        prod = 1
        for ele in nums:
            prefix_arr.append(prod)
            prod *= ele

    nums = nums[::-1]

        prod = 1
        length = len(nums)-1
        for idx, ele in enumerate(nums):
            prefix_arr[length-idx] = prefix_arr[length-idx]*prod 
            prod *= ele

    return prefix_arr

Question 5

Maximum sum subarray

Answer 5

Idea:
If a number is greater than the max sum of a subarray till this point, then the subarray with max sum should start from this index
Logic:
keep current sum and max sum as 0th index value
1 Loop over the array starting the 1st index
2. calculate the current sum as max of current value and current value + max sum till this point
the 3. output will be the max of all small maximum sum subarrays

    def maxSubArray(self, A):
        if not A:
            return 0

    curSum = maxSum = A[0]
    for num in A[1:]:
        curSum = max(num, curSum + num)
        maxSum = max(maxSum, curSum)

    return maxSum

Question 6

Find max product of three numbers in an array

Answer 6

Idea:

Iterate over the array once and keep track of highest, highest_product_of_2, highest_product_of_3, lowest, lowest_product_of_2, lowest_product_of_3 at each point

Logic:

1. Initialize above variable till index 2
2. Loop over the array from idx 2 to length of array
3. Keep updating the above variables
4. highest_prod_3 = max(highest_prod_3, highest_prod_2current, lowest_prod_2current)
5. highest_prod_2 = max(highest_prod_2, highestcurrent, lowestcurrent)
6. Similarly others
7. Return highest_prod_3

def highest_product_of_3(list_of_ints):
    if len(list_of_ints) < 3:
        raise Exception

highest = max(list_of_ints[0], list_of_ints[1])
highest_prod_2 = list_of_ints[0]*list_of_ints[1]
highest_prod_3 = list_of_ints[0]*list_of_ints[1]*list_of_ints[2]

lowest = min(list_of_ints[0],list_of_ints[1]) 
lowest_prod_2 = list_of_ints[0]*list_of_ints[1]
lowest_prod_3 = list_of_ints[0]*list_of_ints[1]*list_of_ints[2]

for idx in range(2, len(list_of_ints)):
    current = list_of_ints[idx]
    highest_prod_3 = max(highest_prod_3, highest_prod_2*current, lowest_prod_2*current)
    highest_prod_2 = max(highest_prod_2, highest*current, lowest*current)
    highest = max(highest, current)

    lowest_prod_3 = min(lowest_prod_3, highest_prod_2*current, lowest_prod_2*current) 
    lowest_prod_2 = min(lowest_prod_2, highest*current, lowest*current)
    lowest = min(lowest, current)

return highest_prod_3