2032: Two Out of Three

Explanation:

We have to return all the numbers which are present in at least two of the three arrays. We are given that all the numbers are in the range of 1 to 100.

Iterate from 1 to 100 and check if the number is present in each of the three arrays and update the count accordingly. If the count is greater than equal to 2, add it to the answer.

Code(Python3):

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        ans = []
        for num in range(1, 101):
            count = 0

            if num in nums1:
                count += 1
            if num in nums2:
                count += 1
            if num in nums3:
                count += 1

            if count >= 2:
                ans.append(num)

        return ans

Time Complexity: O(100 * 3 * n) ~ O(n)

Space Complexity: O(n)

2033: Minimum Operations to Make a Uni-Value Grid

Explanation:

If we can make the grid Uni-value to an element, then all the elements of the grid can be used to make the Uni-value and the optimal element(requiring minimum operations) is the median element from the grid. (Will add proof later).

Code(Python3):

class Solution:
    def minOperations(self, grid: List[List[int]], x: int) -> int:

        m = len(grid)
        n = len(grid[0])

        if m==1 and n==1: 
            return 0

        arr = [] 
        for i in range(m):
            arr.extend(grid[i])

        arr.sort()

        # when n*m is odd, median is arr[len(arr)//2]
        # when n*m is even, arr[len(arr)//2] and arr[len(arr)//2-1] is the median.

        tar1 = arr[len(arr)//2]
        tar2 = arr[len(arr)//2-1]

        #calculate for both cases and return the minimum answer
        return min(self.find_ops_given_target(grid, tar1, x),self.find_ops_given_target(grid, tar2, x))


    def find_ops_given_target(self, grid, tar, x):
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if abs(grid[i][j]-tar)%x!=0:
                    return -1
                else:
                    count += abs(grid[i][j]-tar)//x

        return count

Time Complexity: O(n*m)

Space Complexity: O(n*m)

2034: Stock Price Fluctuation

Explanation:

Use a SortedList to store the stock prices in sorted order. Note that heaps can also be used. Also, use a dictionary to store the value of the stock at a given timestamp. This is required to update later.

Code(Python3):

from sortedcontainers import SortedList
class StockPrice:

    def __init__(self):
        #store stock price in sorted order
        self.l = SortedList()
        #dict to store the the stock price at given timestamp
        self.d = {}
        #stores the latest price of the stock based on the timestamp
        #[time, value]
        self.last = [-float("inf"), 0]


    def update(self, timestamp: int, price: int) -> None:
        #update latest 
        if self.last[0] <= timestamp:
            self.last = [timestamp, price]


        #if new timestamp
        if timestamp not in self.d.keys():
            self.d[timestamp] = price
            self.l.add(price)
        #if timestamp is seen already
        else:
            oldprice = self.d[timestamp]
            self.l.remove(oldprice)
            self.l.add(price)
            self.d[timestamp] = price                   

    def current(self) -> int:
        return self.last[1]


    def maximum(self) -> int:
        return self.l[-1]


    def minimum(self) -> int:
        return self.l[0]

Time Complexity: update() requires O(log(n)) time. Rest of the functions take constant time.

Space Complexity: O(n)

2035: Partition Array Into Two Arrays to Minimize Sum Difference

Explanation: One easy way to do this is to either take the current element or not to take it in the first array, till its size is less than N / 2 and then return the minimum absolute difference. But the time complexity of this approach is \( 2^{30} \) which will result in TLE.

To optimise this, we use

Meet in the Middle approach.

In this, we generate all possible sums of subsets of the lengths from 0 to N/2 from the left half and right half of our original array. Now suppose we choose i elements from the left half. We need to choose N/2 - i elements from our right half. We will choose those elements such that the following value is minimised : $$ abs(S / 2 - (leftSum + rightSum)) $$ , where S = sum of original array, leftSum = sum of the i elements from left half and rightSum = sum of N/2 - i elements from right half. We can do this by binary searching S/2 - leftSum in all the rightSums of N/2 - i elements.

Code(Python3):

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        N = len(nums)
        #base case if all elements from left half are part of the partition, i = 0
        ans = abs(sum(nums[:N//2]) - sum(nums[N//2:]))
        S = sum(nums)

        #consider i elements from left half in first array
        for i in range(1, N // 2):
            #sum of all combinations of length i from left half
            leftSums = [sum(comb) for comb in combinations(nums[:N // 2], i)]

            #sum of all combinations of length N/2 - i from right half
            rightSums = [sum(comb) for comb in combinations(nums[N // 2:], N // 2 - i)]
            rightSums.sort()

            for leftSum in leftSums:
                #idealRightSum is the sum when diff would be zero
                idealRightSum = S // 2 - leftSum
                pos = bisect.bisect_left(rightSums, idealRightSum) 
                if 0 <= pos < len(rightSums):
                    left_half_sum = leftSum + rightSums[pos]
                    right_half_sum = S - left_half_sum
                    diff = abs(left_half_sum - right_half_sum)
                    ans = min(ans, diff) 
        return ans

Time Complexity: O(N/2 * 2 ^ (N/2))

Space Complexity: O(2 ^ (N/2))