avatar_url

Sandesh Rana | Python

I'm a developer from Himalayas, with a passion for crafting efficient and elegant code, with creativity and precision.

Divide and Conquer

21 Aug 2024 » programming, algorithm

Divide and Conquer: Easy to Hard Problems

Easy

  1. Merge Sort (Implementation of the merge sort algorithm)
  2. Binary Search (Basic binary search on a sorted array)
  3. Quick Sort (Implementation of the quick sort algorithm)
  4. Count Inversions (Counts the number of inversions in an array using merge sort)
  5. Find Peak Element (Finds a peak element in an array with divide and conquer)

Medium

  1. Median of Two Sorted Arrays (Finds the median of two sorted arrays using binary search)
  2. Closest Pair of Points(Finds the closest pair of points in a 2D plane using divide and conquer)
  3. Find Kth Largest Element in an Array (Finds the Kth largest element using quick select)
  4. Strassen’s Matrix Multiplication (Optimized matrix multiplication using divide and conquer)
  5. Count of Smaller Numbers After Self (Counts the number of smaller elements after each element using merge sort)

Hard

  1. Maximum Subarray Sum with One Deletion (Finds the maximum subarray sum with at most one deletion)
  2. Matrix Chain Multiplication (Finds the optimal way to multiply a given sequence of matrices)
  3. Largest Rectangle in Histogram (Finds the largest rectangle area in a histogram using divide and conquer)
  4. Kth Smallest Element in a Sorted Matrix (Finds the Kth smallest element in a sorted matrix using binary search)
  5. 4Sum (Finds all unique quadruplets in an array that sum up to a target value)