Problems

Master divide and conquer by solving these carefully selected problems. Each problem demonstrates different applications of the divide and conquer paradigm and builds your algorithmic skills progressively.

For reusable code blocks and standard algorithms, refer to the Code Templates page.

Problem Categories

Easy Problems

1. Merge Two Sorted Lists

LeetCode 21 | Difficulty: Easy | Acceptance: 63.2%

Brief: Merge two sorted linked lists and return it as a sorted list.
Why this pattern?: Demonstrates the “Combine” step of Merge Sort in isolation.
Key Insight: Compare the heads of the two lists, pick the smaller one, and recursively merge the rest.

Visual Explanation:

  graph LR
    L1[List 1: 1 -> 2 -> 4]
    L2[List 2: 1 -> 3 -> 4]
    M[Merged: 1 -> 1 -> 2 -> 3 -> 4 -> 4]
    L1 & L2 -->|Compare Heads| M

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
function mergeTwoLists(list1, list2) {
    if (!list1) return list2;
    if (!list2) return list1;

    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1

        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;

        if (list1->val <= list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }
    if list2 == nil {
        return list1
    }

    if list1.Val <= list2.Val {
        list1.Next = mergeTwoLists(list1.Next, list2)
        return list1
    } else {
        list2.Next = mergeTwoLists(list1, list2.Next)
        return list2
    }
}

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
def merge_two_lists(list1, list2)
    return list2 if list1.nil?
    return list1 if list2.nil?

    if list1.val <= list2.val
        list1.next = merge_two_lists(list1.next, list2)
        return list1
    else
        list2.next = merge_two_lists(list1, list2.next)
        return list2
    end
end

2. Valid Perfect Square

LeetCode 367 | Difficulty: Easy | Acceptance: 42.8%

Brief: Given a positive integer num, return true if num is a perfect square.
Why this pattern?: Use Binary Search to find if mid * mid == num.
Key Insight: The search space is 1 to num. If mid * mid > num, the root must be smaller.

Visual Explanation:

  graph TD
    Range[1 ... num] -->|Mid| Check{mid*mid == num?}
    Check -->|Yes| True[Return True]
    Check -->|No| Compare{mid*mid > num?}
    Compare -->|Yes| Lower[Search 1 ... mid-1]
    Compare -->|No| Higher[Search mid+1 ... num]

function isPerfectSquare(num) {
    let left = 1, right = num;

    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        let square = mid * mid;

        if (square === num) return true;

        if (square > num) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return false;
}

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left, right = 1, num

        while left <= right:
            mid = (left + right) // 2
            square = mid * mid

            if square == num:
                return True
            elif square > num:
                right = mid - 1
            else:
                left = mid + 1

        return False

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 1, right = num;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;

            if (square == num) return true;

            if (square > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool isPerfectSquare(int num) {
        long long left = 1, right = num;

        while (left <= right) {
            long long mid = left + (right - left) / 2;
            long long square = mid * mid;

            if (square == num) return true;

            if (square > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
};

func isPerfectSquare(num int) bool {
    left, right := 1, num

    for left <= right {
        mid := left + (right - left) / 2
        square := mid * mid

        if square == num {
            return true
        } else if square > num {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return false
}

def is_perfect_square(num)
    left, right = 1, num

    while left <= right
        mid = (left + right) / 2
        square = mid * mid

        if square == num
            return true
        elsif square > num
            right = mid - 1
        else
            left = mid + 1
        end
    end

    false
end

Medium Problems

3. Sort an Array

LeetCode 912 | Difficulty: Medium | Acceptance: 62.7%

Brief: Sort an array of integers in ascending order.
Why this pattern?: Implement Merge Sort to guarantee $O(N \log N)$ time.
Key Insight: Divide input into two halves, recursively sort them, then merge the sorted halves.

Visual Explanation:

  graph TD
    A[5 2 3 1] -->|Divide| B[5 2]
    A -->|Divide| C[3 1]
    B -->|Divide| D[5] & E[2]
    C -->|Divide| F[3] & G[1]
    D & E -->|Combine| H[2 5]
    F & G -->|Combine| I[1 3]
    H & I -->|Combine| J[1 2 3 5]

function sortArray(nums) {
    function mergeSort(arr, left, right) {
        if (left >= right) return;

        const mid = Math.floor((left + right) / 2);
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    function merge(arr, left, mid, right) {
        const n1 = mid - left + 1;
        const n2 = right - mid;
        const leftArr = new Array(n1);
        const rightArr = new Array(n2);

        for (let i = 0; i < n1; i++) leftArr[i] = arr[left + i];
        for (let j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];

        let i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
            else arr[k++] = rightArr[j++];
        }
        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }

    mergeSort(nums, 0, nums.length - 1);
    return nums;
}

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge_sort(arr, left, right):
            if left >= right: return
            mid = (left + right) // 2
            merge_sort(arr, left, mid)
            merge_sort(arr, mid + 1, right)
            merge(arr, left, mid, right)

        def merge(arr, left, mid, right):
            left_arr = arr[left:mid + 1]
            right_arr = arr[mid + 1:right + 1]
            i = j = 0
            k = left
            while i < len(left_arr) and j < len(right_arr):
                if left_arr[i] <= right_arr[j]:
                    arr[k] = left_arr[i]
                    i += 1
                else:
                    arr[k] = right_arr[j]
                    j += 1
                k += 1
            while i < len(left_arr):
                arr[k] = left_arr[i]
                i += 1
                k += 1
            while j < len(right_arr):
                arr[k] = right_arr[j]
                j += 1
                k += 1

        merge_sort(nums, 0, len(nums) - 1)
        return nums

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
            else arr[k++] = rightArr[j++];
        }
        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }
}

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void mergeSort(vector<int>& arr, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    void merge(vector<int>& arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        vector<int> leftArr(n1), rightArr(n2);

        for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
            else arr[k++] = rightArr[j++];
        }
        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }
};

func sortArray(nums []int) []int {
    mergeSort(nums, 0, len(nums)-1)
    return nums
}

func mergeSort(arr []int, left, right int) {
    if left >= right {
        return
    }
    mid := left + (right-left)/2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)
    merge(arr, left, mid, right)
}

func merge(arr []int, left, mid, right int) {
    n1 := mid - left + 1
    n2 := right - mid
    leftArr := make([]int, n1)
    rightArr := make([]int, n2)

    for i := 0; i < n1; i++ { leftArr[i] = arr[left+i] }
    for j := 0; j < n2; j++ { rightArr[j] = arr[mid+1+j] }

    i, j, k := 0, 0, left
    for i < n1 && j < n2 {
        if leftArr[i] <= rightArr[j] {
            arr[k] = leftArr[i]; i++
        } else {
            arr[k] = rightArr[j]; j++
        }
        k++
    }
    for i < n1 { arr[k] = leftArr[i]; i++; k++ }
    for j < n2 { arr[k] = rightArr[j]; j++; k++ }
}

def sort_array(nums)
    merge_sort(nums, 0, nums.length - 1)
    nums
end

def merge_sort(arr, left, right)
    return if left >= right
    mid = (left + right) / 2
    merge_sort(arr, left, mid)
    merge_sort(arr, mid + 1, right)
    merge(arr, left, mid, right)
end

def merge(arr, left, mid, right)
    left_arr = arr[left..mid]
    right_arr = arr[mid + 1..right]

    i, j, k = 0, 0, left
    while i < left_arr.length && j < right_arr.length
        if left_arr[i] <= right_arr[j]
            arr[k] = left_arr[i]; i += 1
        else
            arr[k] = right_arr[j]; j += 1
        end
        k += 1
    end
    while i < left_arr.length
        arr[k] = left_arr[i]; i += 1; k += 1
    end
    while j < right_arr.length
        arr[k] = right_arr[j]; j += 1; k += 1
    end
end

Hard Problems

4. Median of Two Sorted Arrays

LeetCode 4 | Difficulty: Hard | Acceptance: 35.4%

Brief: Find the median of two sorted arrays with $O(\log (M+N))$ complexity.
Why this pattern?: Use Binary Search to find the correct partition point in the smaller array.
Key Insight: Partition both arrays such that all elements on the left are smaller than elements on the right.

Visual Explanation:

  graph TD
    Arrays[Nums1, Nums2] -->|Partition| Part1["Left1 | Right1"]
    Arrays -->|Partition| Part2["Left2 | Right2"]
    Part1 & Part2 -->|Valid?| Check{"MaxLeft <= MinRight?"}
    Check -->|Yes| Median[Calc Median]
    Check -->|No| Shift[Shift Partition]

function findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];

    const m = nums1.length;
    const n = nums2.length;
    let left = 0, right = m;

    while (left <= right) {
        const i = Math.floor((left + right) / 2);
        const j = Math.floor((m + n + 1) / 2) - i;

        const maxLeft1 = (i === 0) ? -Infinity : nums1[i - 1];
        const minRight1 = (i === m) ? Infinity : nums1[i];
        const maxLeft2 = (j === 0) ? -Infinity : nums2[j - 1];
        const minRight2 = (j === n) ? Infinity : nums2[j];

        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((m + n) % 2 === 0) {
                return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
            } else {
                return Math.max(maxLeft1, maxLeft2);
            }
        } else if (maxLeft1 > minRight2) {
            right = i - 1;
        } else {
            left = i + 1;
        }
    }
}

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

        m, n = len(nums1), len(nums2)
        left, right = 0, m

        while left <= right:
            i = (left + right) // 2
            j = (m + n + 1) // 2 - i

            maxLeft1 = float('-inf') if i == 0 else nums1[i - 1]
            minRight1 = float('inf') if i == m else nums1[i]
            maxLeft2 = float('-inf') if j == 0 else nums2[j - 1]
            minRight2 = float('inf') if j == n else nums2[j]

            if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
                if (m + n) % 2 == 0:
                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
                else:
                    return max(maxLeft1, maxLeft2)
            elif maxLeft1 > minRight2:
                right = i - 1
            else:
                left = i + 1

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m;

        while (left <= right) {
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;

            int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
                } else {
                    return Math.max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
        return 0.0;
    }
}

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);

        int m = nums1.size();
        int n = nums2.size();
        int left = 0, right = m;

        while (left <= right) {
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;

            int maxLeft1 = (i == 0) ? INT_MIN : nums1[i - 1];
            int minRight1 = (i == m) ? INT_MAX : nums1[i];
            int maxLeft2 = (j == 0) ? INT_MIN : nums2[j - 1];
            int minRight2 = (j == n) ? INT_MAX : nums2[j];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((m + n) % 2 == 0) {
                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
                } else {
                    return max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                right = i - 1;
            } else {
                left = i + 1;
            }
        }
        return 0.0;
    }
};

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    if len(nums1) > len(nums2) {
        return findMedianSortedArrays(nums2, nums1)
    }

    m, n := len(nums1), len(nums2)
    left, right := 0, m

    for left <= right {
        i := (left + right) / 2
        j := (m + n + 1) / 2 - i

        maxLeft1 := math.MinInt64
        if i > 0 { maxLeft1 = nums1[i-1] }

        minRight1 := math.MaxInt64
        if i < m { minRight1 = nums1[i] }

        maxLeft2 := math.MinInt64
        if j > 0 { maxLeft2 = nums2[j-1] }

        minRight2 := math.MaxInt64
        if j < n { minRight2 = nums2[j] }

        if maxLeft1 <= minRight2 && maxLeft2 <= minRight1 {
            if (m + n) % 2 == 0 {
                return float64(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
            } else {
                return float64(max(maxLeft1, maxLeft2))
            }
        } else if maxLeft1 > minRight2 {
            right = i - 1
        } else {
            left = i + 1
        }
    }
    return 0.0
}

func max(a, b int) int { if a > b { return a }; return b }
func min(a, b int) int { if a < b { return a }; return b }

def find_median_sorted_arrays(nums1, nums2)
    return find_median_sorted_arrays(nums2, nums1) if nums1.length > nums2.length

    m, n = nums1.length, nums2.length
    left, right = 0, m

    while left <= right
        i = (left + right) / 2
        j = (m + n + 1) / 2 - i

        max_left1 = (i == 0) ? -Float::INFINITY : nums1[i - 1]
        min_right1 = (i == m) ? Float::INFINITY : nums1[i]
        max_left2 = (j == 0) ? -Float::INFINITY : nums2[j - 1]
        min_right2 = (j == n) ? Float::INFINITY : nums2[j]

        if max_left1 <= min_right2 && max_left2 <= min_right1
            if (m + n) % 2 == 0
                return ([max_left1, max_left2].max + [min_right1, min_right2].min) / 2.0
            else
                return [max_left1, max_left2].max.to_f
            end
        elsif max_left1 > min_right2
            right = i - 1
        else
            left = i + 1
        end
    end
end

5. Count of Smaller Numbers After Self

LeetCode 315 | Difficulty: Hard | Acceptance: 44.9%

Brief: Count how many numbers smaller than nums[i] appear to the right of nums[i].
Why this pattern?: Modified Merge Sort moves smaller elements from right to left, allowing us to count “jumps”.
Key Insight: During merge, if we pick an element from the right half, it “jumps” over remaining elements in the left half, contributing to inversions.

Visual Explanation:

  graph TD
    Merged[Merge Process]
    Left[Left: 5 2]
    Right[Right: 6 1]
    Left & Right -->|Merge| Merged
    Merged -->|Count Jumps| Counts[Update Counts]

function countSmaller(nums) {
    const counts = new Array(nums.length).fill(0);
    const indices = nums.map((_, i) => i);

    function mergeSort(left, right) {
        if (left >= right) return;
        const mid = Math.floor((left + right) / 2);
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, mid, right);
    }

    function merge(left, mid, right) {
        const leftArr = indices.slice(left, mid + 1);
        const rightArr = indices.slice(mid + 1, right + 1);
        let i = 0, j = 0, k = left;
        let rightCounter = 0;

        while (i < leftArr.length && j < rightArr.length) {
            if (nums[leftArr[i]] <= nums[rightArr[j]]) {
                counts[leftArr[i]] += rightCounter;
                indices[k++] = leftArr[i++];
            } else {
                rightCounter++;
                indices[k++] = rightArr[j++];
            }
        }

        while (i < leftArr.length) {
            counts[leftArr[i]] += rightCounter;
            indices[k++] = leftArr[i++];
        }
        while (j < rightArr.length) {
            indices[k++] = rightArr[j++];
        }
    }

    mergeSort(0, nums.length - 1);
    return counts;
}

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        counts = [0] * len(nums)
        indices = list(range(len(nums)))

        def merge_sort(left, right):
            if left >= right: return
            mid = (left + right) // 2
            merge_sort(left, mid)
            merge_sort(mid + 1, right)
            merge(left, mid, right)

        def merge(left, mid, right):
            left_arr = indices[left:mid + 1]
            right_arr = indices[mid + 1:right + 1]
            i = j = 0
            k = left
            right_counter = 0

            while i < len(left_arr) and j < len(right_arr):
                if nums[left_arr[i]] <= nums[right_arr[j]]:
                    counts[left_arr[i]] += right_counter
                    indices[k] = left_arr[i]
                    i += 1
                else:
                    right_counter += 1
                    indices[k] = right_arr[j]
                    j += 1
                k += 1

            while i < len(left_arr):
                counts[left_arr[i]] += right_counter
                indices[k] = left_arr[i]
                i += 1; k += 1
            while j < len(right_arr):
                indices[k] = right_arr[j]
                j += 1; k += 1

        merge_sort(0, len(nums) - 1)
        return counts

class Solution {
    int[] counts;
    int[] indices;

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        counts = new int[n];
        indices = new int[n];
        for (int i = 0; i < n; i++) indices[i] = i;

        mergeSort(nums, 0, n - 1);

        List<Integer> result = new ArrayList<>();
        for (int c : counts) result.add(c);
        return result;
    }

    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int[] leftArr = new int[mid - left + 1];
        int[] rightArr = new int[right - mid];

        for (int i = 0; i < leftArr.length; i++) leftArr[i] = indices[left + i];
        for (int i = 0; i < rightArr.length; i++) rightArr[i] = indices[mid + 1 + i];

        int i = 0, j = 0, k = left;
        int rightCounter = 0;

        while (i < leftArr.length && j < rightArr.length) {
            if (nums[leftArr[i]] <= nums[rightArr[j]]) {
                counts[leftArr[i]] += rightCounter;
                indices[k++] = leftArr[i++];
            } else {
                rightCounter++;
                indices[k++] = rightArr[j++];
            }
        }

        while (i < leftArr.length) {
            counts[leftArr[i]] += rightCounter;
            indices[k++] = leftArr[i++];
        }
        while (j < rightArr.length) {
            indices[k++] = rightArr[j++];
        }
    }
}

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> counts(n, 0);
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);

        mergeSort(nums, indices, counts, 0, n - 1);
        return counts;
    }

    void mergeSort(vector<int>& nums, vector<int>& indices, vector<int>& counts, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, indices, counts, left, mid);
        mergeSort(nums, indices, counts, mid + 1, right);
        merge(nums, indices, counts, left, mid, right);
    }

    void merge(vector<int>& nums, vector<int>& indices, vector<int>& counts, int left, int mid, int right) {
        vector<int> leftArr, rightArr;
        for(int i = left; i <= mid; i++) leftArr.push_back(indices[i]);
        for(int i = mid + 1; i <= right; i++) rightArr.push_back(indices[i]);

        int i = 0, j = 0, k = left;
        int rightCounter = 0;

        while (i < leftArr.size() && j < rightArr.size()) {
            if (nums[leftArr[i]] <= nums[rightArr[j]]) {
                counts[leftArr[i]] += rightCounter;
                indices[k++] = leftArr[i++];
            } else {
                rightCounter++;
                indices[k++] = rightArr[j++];
            }
        }

        while (i < leftArr.size()) {
            counts[leftArr[i]] += rightCounter;
            indices[k++] = leftArr[i++];
        }
        while (j < rightArr.size()) {
            indices[k++] = rightArr[j++];
        }
    }
};

func countSmaller(nums []int) []int {
    n := len(nums)
    counts := make([]int, n)
    indices := make([]int, n)
    for i := 0; i < n; i++ { indices[i] = i }

    var mergeSort func(int, int)
    var merge func(int, int, int)

    merge = func(left, mid, right int) {
        leftArr := make([]int, mid-left+1)
        rightArr := make([]int, right-mid)
        copy(leftArr, indices[left:mid+1])
        copy(rightArr, indices[mid+1:right+1])

        i, j, k := 0, 0, left
        rightCounter := 0

        for i < len(leftArr) && j < len(rightArr) {
            if nums[leftArr[i]] <= nums[rightArr[j]] {
                counts[leftArr[i]] += rightCounter
                indices[k] = leftArr[i]
                i++
            } else {
                rightCounter++
                indices[k] = rightArr[j]
                j++
            }
            k++
        }
        for i < len(leftArr) {
            counts[leftArr[i]] += rightCounter
            indices[k] = leftArr[i]
            i++; k++
        }
        for j < len(rightArr) {
            indices[k] = rightArr[j]
            j++; k++
        }
    }

    mergeSort = func(left, right int) {
        if left >= right { return }
        mid := left + (right-left)/2
        mergeSort(left, mid)
        mergeSort(mid+1, right)
        merge(left, mid, right)
    }

    mergeSort(0, n-1)
    return counts
}

def count_smaller(nums)
    counts = Array.new(nums.length, 0)
    indices = (0...nums.length).to_a

    merge_sort(nums, indices, counts, 0, nums.length - 1)
    counts
end

def merge_sort(nums, indices, counts, left, right)
    return if left >= right
    mid = (left + right) / 2
    merge_sort(nums, indices, counts, left, mid)
    merge_sort(nums, indices, counts, mid + 1, right)
    merge(nums, indices, counts, left, mid, right)
end

def merge(nums, indices, counts, left, mid, right)
    left_arr = indices[left..mid]
    right_arr = indices[mid + 1..right]

    i = 0; j = 0; k = left
    right_counter = 0

    while i < left_arr.length && j < right_arr.length
        if nums[left_arr[i]] <= nums[right_arr[j]]
            counts[left_arr[i]] += right_counter
            indices[k] = left_arr[i]
            i += 1
        else
            right_counter += 1
            indices[k] = right_arr[j]
            j += 1
        end
        k += 1
    end

    while i < left_arr.length
        counts[left_arr[i]] += right_counter
        indices[k] = left_arr[i]
        i += 1; k += 1
    end

    while j < right_arr.length
        indices[k] = right_arr[j]
        j += 1; k += 1
    end
end

6. The Skyline Problem

LeetCode 218 | Difficulty: Hard | Acceptance: 38.7%

Brief: Return the key points of the skyline formed by buildings.
Why this pattern?: Split buildings into two sets, solve recursively, then merge the two skylines.
Key Insight: Merging two 2D skylines is similar to merging sorted lists, but tracking heights.

Visual Explanation:

  graph TD
    S1[Skyline Left] -->|Merge| M[Merged Skyline]
    S2[Skyline Right] -->|Merge| M
    M -->|Result| R[[x, max_height]]

function getSkyline(buildings) {
    if (buildings.length === 0) return [];
    if (buildings.length === 1) {
        const [l, r, h] = buildings[0];
        return [[l, h], [r, 0]];
    }

    const mid = Math.floor(buildings.length / 2);
    const leftSkyline = getSkyline(buildings.slice(0, mid));
    const rightSkyline = getSkyline(buildings.slice(mid));

    return merge(leftSkyline, rightSkyline);
}

function merge(left, right) {
    const res = [];
    let h1 = 0, h2 = 0;
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        let x = 0, h = 0;
        if (left[i][0] < right[j][0]) {
            x = left[i][0];
            h1 = left[i][1];
            i++;
        } else if (left[i][0] > right[j][0]) {
            x = right[j][0];
            h2 = right[j][1];
            j++;
        } else {
            x = left[i][0];
            h1 = left[i][1];
            h2 = right[j][1];
            i++; j++;
        }
        h = Math.max(h1, h2);
        if (res.length === 0 || res[res.length - 1][1] !== h) {
            res.push([x, h]);
        }
    }
    while (i < left.length) res.push(left[i++]);
    while (j < right.length) res.push(right[j++]);
    return res;
}

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        if not buildings: return []
        if len(buildings) == 1:
            l, r, h = buildings[0]
            return [[l, h], [r, 0]]

        mid = len(buildings) // 2
        left = self.getSkyline(buildings[:mid])
        right = self.getSkyline(buildings[mid:])
        return self.merge(left, right)

    def merge(self, left, right):
        res = []
        h1 = h2 = 0
        i = j = 0

        while i < len(left) and j < len(right):
            x = 0
            if left[i][0] < right[j][0]:
                x = left[i][0]
                h1 = left[i][1]
                i += 1
            elif left[i][0] > right[j][0]:
                x = right[j][0]
                h2 = right[j][1]
                j += 1
            else:
                x = left[i][0]
                h1 = left[i][1]
                h2 = right[j][1]
                i += 1; j += 1

            h = max(h1, h2)
            if not res or res[-1][1] != h:
                res.append([x, h])

        res.extend(left[i:])
        res.extend(right[j:])
        return res

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        if (buildings.length == 0) return new ArrayList<>();
        return divide(buildings, 0, buildings.length - 1);
    }

    private List<List<Integer>> divide(int[][] buildings, int l, int r) {
        if (l == r) {
            List<List<Integer>> res = new ArrayList<>();
            res.add(Arrays.asList(buildings[l][0], buildings[l][2]));
            res.add(Arrays.asList(buildings[l][1], 0));
            return res;
        }
        int mid = l + (r - l) / 2;
        List<List<Integer>> left = divide(buildings, l, mid);
        List<List<Integer>> right = divide(buildings, mid + 1, r);
        return merge(left, right);
    }

    private List<List<Integer>> merge(List<List<Integer>> left, List<List<Integer>> right) {
        List<List<Integer>> res = new ArrayList<>();
        int h1 = 0, h2 = 0;
        int i = 0, j = 0;

        while (i < left.size() && j < right.size()) {
            int x = 0, h = 0;
            int x1 = left.get(i).get(0);
            int x2 = right.get(j).get(0);

            if (x1 < x2) {
                x = x1;
                h1 = left.get(i).get(1);
                i++;
            } else if (x1 > x2) {
                x = x2;
                h2 = right.get(j).get(1);
                j++;
            } else {
                x = x1;
                h1 = left.get(i).get(1);
                h2 = right.get(j).get(1);
                i++; j++;
            }
            h = Math.max(h1, h2);
            if (res.isEmpty() || res.get(res.size() - 1).get(1) != h) {
                res.add(Arrays.asList(x, h));
            }
        }
        while (i < left.size()) res.add(left.get(i++));
        while (j < right.size()) res.add(right.get(j++));
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        if (buildings.empty()) return {};
        return divide(buildings, 0, buildings.size() - 1);
    }

    vector<vector<int>> divide(vector<vector<int>>& buildings, int l, int r) {
        if (l == r) {
            return {{buildings[l][0], buildings[l][2]}, {buildings[l][1], 0}};
        }
        int mid = l + (r - l) / 2;
        vector<vector<int>> left = divide(buildings, l, mid);
        vector<vector<int>> right = divide(buildings, mid + 1, r);
        return merge(left, right);
    }

    vector<vector<int>> merge(vector<vector<int>>& left, vector<vector<int>>& right) {
        vector<vector<int>> res;
        int h1 = 0, h2 = 0;
        int i = 0, j = 0;

        while (i < left.size() && j < right.size()) {
            int x = 0, h = 0;
            if (left[i][0] < right[j][0]) {
                x = left[i][0];
                h1 = left[i][1];
                i++;
            } else if (left[i][0] > right[j][0]) {
                x = right[j][0];
                h2 = right[j][1];
                j++;
            } else {
                x = left[i][0];
                h1 = left[i][1];
                h2 = right[j][1];
                i++; j++;
            }
            h = max(h1, h2);
            if (res.empty() || res.back()[1] != h) {
                res.push_back({x, h});
            }
        }
        while (i < left.size()) res.push_back(left[i++]);
        while (j < right.size()) res.push_back(right[j++]);
        return res;
    }
};

func getSkyline(buildings [][]int) [][]int {
    if len(buildings) == 0 { return nil }
    return divide(buildings, 0, len(buildings)-1)
}

func divide(buildings [][]int, l, r int) [][]int {
    if l == r {
        return [][]int{{buildings[l][0], buildings[l][2]}, {buildings[l][1], 0}}
    }
    mid := l + (r-l)/2
    left := divide(buildings, l, mid)
    right := divide(buildings, mid+1, r)
    return merge(left, right)
}

func merge(left, right [][]int) [][]int {
    res := [][]int{}
    h1, h2 := 0, 0
    i, j := 0, 0

    for i < len(left) && j < len(right) {
        x, h := 0, 0
        if left[i][0] < right[j][0] {
            x = left[i][0]
            h1 = left[i][1]
            i++
        } else if left[i][0] > right[j][0] {
            x = right[j][0]
            h2 = right[j][1]
            j++
        } else {
            x = left[i][0]
            h1 = left[i][1]
            h2 = right[j][1]
            i++; j++
        }
        if h1 > h2 { h = h1 } else { h = h2 }
        if len(res) == 0 || res[len(res)-1][1] != h {
            res = append(res, []int{x, h})
        }
    }
    res = append(res, left[i:]...)
    res = append(res, right[j:]...)
    return res
}

def get_skyline(buildings)
    return [] if buildings.empty?
    return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]] if buildings.length == 1

    mid = buildings.length / 2
    left_skyline = get_skyline(buildings[0...mid])
    right_skyline = get_skyline(buildings[mid..-1])

    merge_skylines(left_skyline, right_skyline)
end

def merge_skylines(left, right)
    result = []
    h1, h2 = 0, 0
    i, j = 0, 0

    while i < left.length && j < right.length
        x = 0
        if left[i][0] < right[j][0]
            x = left[i][0]
            h1 = left[i][1]
            i += 1
        elsif left[i][0] > right[j][0]
            x = right[j][0]
            h2 = right[j][1]
            j += 1
        else
            x = left[i][0]
            h1 = left[i][1]
            h2 = right[j][1]
            i += 1; j += 1
        end

        max_h = [h1, h2].max
        if result.empty? || result.last[1] != max_h
            result << [x, max_h]
        end
    end

    result.concat(left[i..-1])
    result.concat(right[j..-1])
    result
end

Recommended Study Order

Merge Two Sorted Lists (Easy): Start here to understand the “Combine” step in isolation.
Sort an Array (Medium): Implement the full Merge Sort algorithm.
Valid Perfect Square (Easy): Practice Binary Search, the other pillar of Divide and Conquer.
Count of Smaller Numbers After Self (Hard): Modify Merge Sort to track additional information (inversions/jumps).
The Skyline Problem (Hard): Apply the merge logic to geometry.
Median of Two Sorted Arrays (Hard): Challenge yourself with complex partitioning logic.