Hard (8)

1. Pascal's Triangle
   1. 21 March, 2026: 00.13.41 ❌
      • Failed at optimization
        1. Bruteforces: Time: $O(n^2)$, Space: $O(n^2)$
        2. Optimal(Binomial Coeffecient: $C(n, k) = C(n, n-k)$): Time: $O(n)$, Space: $O(n)$
2. Majority Elements
   1. 06 April, 2026: 00.24.54 ❌

      count(a) > n/3
      count(b) > n/3
      count(c) > n/3
      (n/3)+(n/3)+(n/3)
      = 3n/3
      = n

      • If any item is greater than n/3, then total become more than n
      • Thats why maxium two item can be more than n/3(minium 1 bigger) and one item must be less than n/3(minimum two less)
      • When one count have 0, that mean whatever is the corresponding candidate, it doesn't make sense.
      • It have 3 part:
        • If count == 0 → set candidate = x
        • If x == candidate → count++
        • Else → count--
      • Handle the duplicate case in the response.
3. Three Sum
   • Inner Loop Replaced by Two Pointer and array must be sorted
   • Handle duplicate for all the pointer(skip if the previous one is same as array need to be sorted)
4. 4-Sum Problem
5. Count number of subarrays with given xor K
   • GeeksforGeeks
   • LeetCode
6. Merge Overlapping Subintervals
7. Merge two sorted arrays without extra space
   • Forward Iteration
     • You don’t overwrite unprocessed elements.
     • You process elements in natural order.
   • Backward Iteration
     • You write into the same array you are reading from, and writing might overwrite elements you haven’t processed yet.
     • You want to avoid shifting elements repeatedly (O(1) space solution).
8. Find Repeated and Missing Numbers
   1. 20 March, 2026: 00.07.12 ✔
9. Count Inversions
   1. 20 March, 2026: 00.12.53 ❌
      • Failed at counting
      1. Identify Where Inversions Occur
         • Inversions occur across the two halves (not within a single half, since those are sorted recursively).
         • During the merge step, if an element from the right half is placed before an element from the left half, it forms inversions with all remaining elements in the left half.

         Left = [2, 4, 6]
         Right = [1, 5, 7]

         • While merging:
           • Compare 2 and 1 → 1 is smaller → inversion count increases by number of remaining elements in Left (2,4,6 → 3 elements).
           • Compare 2 and 5 → no inversion, continue.
           • Compare 4 and 5 → no inversion, continue.
           • Compare 6 and 5 → 5 is smaller → inversion count increases by remaining elements in Left (6 → 1 element).
      2. Modify the Merge Function
         While merging two sorted arrays L and R:
         • If L[i] <= R[j] → take L[i], no new inversions.
         • Else (i.e., L[i] > R[j]):
           • Take R[j] into the merged array.
           • Add (len(L) - i) to cnt because all remaining elements in L from i onwards are greater than R[j].
10. Reverse Pairs

• Bruteforce failed, apply sorting alorithm for better pair comparison. Don't worry about the order of the item as the problem want the element, not their index

• A reverse pair is defined as:

  nums[i] > 2 * nums[j]  where i < j

  You need to count these before merging. Usually, during merge sort:

  Before merging the two halves, for each i in left array, count how many js in right array satisfy nums[i] > 2 * nums[j]. Add this count to your total.

12. Maximum Product Subarray
    1. 20 March, 2026: 00.16.37 ❌
       • Failed at implementation
         • Track current max and current min, Because the minimum can become maximum after multiplying by a negative.
         • A negative number can turn min → max and max → min