Day 14 – Inversions, Max Product Subarray, Merge Intervals, In-Place Merging, Duplicates, and Binary Search Patterns

Count Inversions (Merge Sort Based)

Counts pairs (i, j) such that i < j and arr[i] > arr[j].

int merge(vector<int>& arr, int low, int mid, int high) {
    vector<int> temp;
    int i = low, j = mid + 1, cnt = 0;

    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else {
            temp.push_back(arr[j++]);
            cnt += (mid - i + 1);  // elements left in left half
        }
    }
    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= high) temp.push_back(arr[j++]);
    for (int k = low; k <= high; k++) arr[k] = temp[k - low];
    return cnt;
}

int mergeSort(vector<int>& arr, int low, int high) {
    int inv = 0;
    if (low < high) {
        int mid = (low + high) / 2;
        inv += mergeSort(arr, low, mid);
        inv += mergeSort(arr, mid + 1, high);
        inv += merge(arr, low, mid, high);
    }
    return inv;
}

// TC: O(n log n)
// SC: O(n)

---

LeetCode 152 – Maximum Product Subarray

Use prefix and suffix scan.

int maxProduct(vector<int>& nums) {
    int n = nums.size(), prod1 = 1, prod2 = 1, res = INT_MIN;
    for (int i = 0; i < n; i++) {
        prod1 *= nums[i];
        prod2 *= nums[n - i - 1];
        res = max(res, max(prod1, prod2));
        if (prod1 == 0) prod1 = 1;
        if (prod2 == 0) prod2 = 1;
    }
    return res;
}
// TC: O(n)
// SC: O(1)

---

Merge Intervals

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res;
    for (auto it : intervals) {
        if (res.empty() || res.back()[1] < it[0])
            res.push_back(it);
        else
            res.back()[1] = max(res.back()[1], it[1]);
    }
    return res;
}
// TC: O(n log n)
// SC: O(n)

---

LeetCode 88 – Merge Sorted Arrays (No Extra Space)

1. Swap + Sort Approach

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = 0;
    while (i >= 0 && j < n && nums1[i] > nums2[j]) {
        swap(nums1[i], nums2[j]);
        i--; j++;
    }
    sort(nums1.begin(), nums1.begin() + m);
    sort(nums2.begin(), nums2.end());
    for (int i = 0; i < n; i++) nums1[m + i] = nums2[i];
}
// TC: O(m log m + n log n)
// SC: O(1)

2. Gap (Shell Sort) Method

void merge(vector<int>& a, int m, vector<int>& b, int n) {
    int gap = (m + n + 1) / 2;
    while (gap > 0) {
        int i = 0, j = gap;
        while (j < m + n) {
            int val1 = (i < m) ? a[i] : b[i - m];
            int val2 = (j < m) ? a[j] : b[j - m];
            if (val1 > val2) {
                if (i < m && j < m) swap(a[i], a[j]);
                else if (i < m) swap(a[i], b[j - m]);
                else swap(b[i - m], b[j - m]);
            }
            i++, j++;
        }
        if (gap == 1) break;
        gap = (gap + 1) / 2;
    }
    for (int i = 0; i < n; i++) a[m + i] = b[i];
}
// TC: O((m+n) log(m+n))
// SC: O(1)

---

LeetCode 287 – Find the Duplicate Number

1. Hashing

int findDuplicate(vector<int>& nums) {
    unordered_set<int> seen;
    for (int n : nums) {
        if (seen.count(n)) return n;
        seen.insert(n);
    }
    return -1;
}
// TC: O(n)
// SC: O(n)

2. Tortoise-Hare (Cycle Detection)

int findDuplicate(vector<int>& nums) {
    int slow = nums[0], fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    fast = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}
// TC: O(n)
// SC: O(1)

---

Binary Search – Pattern, Code

Binary search is used for:

• Sorted arrays

• Searching in space of answers

• Monotonic conditions

Iterative BS

int binarySearch(vector<int>& arr, int target) {
    int l = 0, r = arr.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}
// TC: O(log n)
// SC: O(1)

Recursive BS

int binarySearchRec(vector<int>& arr, int l, int r, int target) {
    if (l > r) return -1;
    int mid = l + (r - l) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) return binarySearchRec(arr, mid + 1, r, target);
    else return binarySearchRec(arr, l, mid - 1, target);
}
// TC: O(log n)
// SC: O(log n) due to recursion stack

---

LeetCode 74 – Search a 2D Matrix

Method 1: Row + BS

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int row = -1;
    for (int i = 0; i < matrix.size(); i++) {
        if (target <= matrix[i].back()) {
            row = i;
            break;
        }
    }
    if (row == -1) return false;

    int l = 0, r = matrix[0].size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (matrix[row][mid] == target) return true;
        else if (matrix[row][mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return false;
}
// TC: O(n + log m)
// SC: O(1)

Method 2: Flattened Matrix (1D BS)

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int l = 0, r = m * n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        int val = matrix[mid / n][mid % n];
        if (val == target) return true;
        else if (val < target) l = mid + 1;
        else r = mid - 1;
    }
    return false;
}
// TC: O(log(m*n))
// SC: O(1)

---

LeetCode 50 – Pow(x, n) (Binary Exponentiation)

double myPow(double x, int n) {
    long long nn = n;
    if (nn < 0) {
        x = 1 / x;
        nn = -nn;
    }
    double res = 1;
    while (nn) {
        if (nn % 2 == 1) res *= x;
        x *= x;
        nn /= 2;
    }
    return res;
}
// TC: O(log n)
// SC: O(1)