DEV Community: Jaspreet singh

Implement a Max Heap

Jaspreet singh — Mon, 22 Jun 2026 11:46:54 +0000

Problem Statement

Implement a Max Heap supporting:

push(x)
pop()
peek()
size()

Intuition

A Max Heap always keeps:

Largest Element at Top

Java provides:

PriorityQueue

which is Min Heap by default.

To create Max Heap:

new PriorityQueue<>(
    Collections.reverseOrder()
);

Java Implementation

class maxHeap {

    PriorityQueue<Integer> pq;

    public maxHeap() {

        pq =
          new PriorityQueue<>(
              Collections.reverseOrder()
          );
    }

    public void push(int x) {
        pq.add(x);
    }

    public void pop() {
        pq.poll();
    }

    public int peek() {

        return pq.isEmpty()
               ? -1
               : pq.peek();
    }

    public int size() {
        return pq.size();
    }
}

Dry Run

push(10)

push(5)

push(20)

Heap:

20
10
5

peek()

Returns:

pop()

Removes:

New Top:

Complexity Analysis

Operation	Complexity
Push	O(log N)
Pop	O(log N)
Peek	O(1)
Size	O(1)

Interview One-Liner

A Max Heap maintains the largest element at the root, allowing efficient insertion and deletion in logarithmic time.

Pattern Learned

Kth Largest
Top K
Merge K Lists
Median Stream

=> Heap

Maximum Sum Combinations

Jaspreet singh — Mon, 22 Jun 2026 11:46:25 +0000

geeksforgeeks.org

Problem Statement

Given two arrays:

A[]
B[]

Find the top K maximum values of:

A[i] + B[j]

Brute Force Intuition

Generate every possible pair:

A[i] + B[j]

Store all sums.

Sort.

Take top K.

Complexity

Time Complexity: O(N² log N²)
Space Complexity: O(N²)

Brute Force Code

for(i)
   for(j)
      sums.add(A[i] + B[j]);

Collections.sort(sums);

Better Approach (Your Code)

Keep only K largest sums using a Min Heap.

PriorityQueue<Integer> pq =
    new PriorityQueue<>();

Generate all pairs.

If heap size exceeds K:

pq.poll();

Complexity

Metric	Complexity
Time	O(N² log K)
Space	O(K)

Moving Towards Optimal

Observation:

After sorting:

Largest pair

=
Largest A
+
Largest B

Suppose:

A = [1,4,2,3]

B = [2,5,1,6]

Sort:

A = [1,2,3,4]

B = [1,2,5,6]

Largest sum:

4 + 6 = 10

After taking:

(i,j)

next candidates are:

(i-1,j)

(i,j-1)

This becomes identical to:

Merge K Sorted Lists

and can be solved using:

Max Heap + Visited Set

Optimal Complexity

Metric	Complexity
Time	O(K log K)
Space	O(K)

Interview One-Liner

Sort both arrays, start from the maximum pair, and use a Max Heap with a visited set to generate only the next best K sums.

Pattern Learned

Top K Pair Values

=> Max Heap
=> Visited Set
=> Sorted Arrays

Kth Largest Element | Heaps

Jaspreet singh — Mon, 22 Jun 2026 11:45:55 +0000

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Note:

Not the kth distinct element.

Brute Force Intuition

In an interview, you can explain it like this:

Sort the entire array in descending order and return the kth element.

Complexity

Time Complexity: O(N log N)
Space Complexity: O(1)

Brute Force Code

Arrays.sort(nums);

return nums[nums.length - k];

Moving Towards the Better Heap Approach

Do we really need the entire sorted array?

No.

We only care about:

Top K largest elements

A Min Heap of size K is sufficient.

Pattern Recognition

Whenever you see:

Kth Largest
Kth Smallest
Top K Elements

Think:

Heap

Better Approach

Maintain a Min Heap.

For every element:

pq.add(num);

If heap size exceeds:

remove smallest.

pq.poll();

At the end:

Top of heap
=
Kth Largest Element

Optimal Java Solution

class Solution {

    public int findKthLargest(int[] nums, int k) {

        PriorityQueue<Integer> pq =
            new PriorityQueue<>();

        for (int num : nums) {

            pq.add(num);

            if (pq.size() > k) {
                pq.poll();
            }
        }

        return pq.peek();
    }
}

Dry Run

Input

nums = [3,2,1,5,6,4]

k = 2

Heap:

3

2 3

1 2 3
remove 1

2 3

2 3 5
remove 2

3 5

3 5 6
remove 3

5 6

4 5 6
remove 4

5 6

Answer:

Complexity Analysis

Metric	Complexity
Time Complexity	O(N log K)
Space Complexity	O(K)

Interview One-Liner

Maintain a Min Heap of size K. The top of the heap always represents the kth largest element seen so far.

Pattern Learned

Top K
+
Largest / Smallest

=> Heap

Aggressive Cows

Jaspreet singh — Sun, 21 Jun 2026 16:24:43 +0000

Problem Statement

Given:

Positions of stalls
k cows

Place the cows in stalls such that:

Minimum distance between any two cows

is maximized.

Return the maximum possible minimum distance.

Brute Force Intuition

In an interview, you can explain it like this:

We can try every possible distance from 1 up to the maximum distance between stalls. For each distance, check whether all cows can be placed while maintaining at least that gap.

This works but is inefficient.

Complexity

Time Complexity: O(N × MaxDistance)
Space Complexity: O(1)

Brute Force Code

for(int dist = 1; dist <= maxDistance; dist++){

    if(canPlaceCows(dist)){
        answer = dist;
    }
}

Moving Towards the Optimal Approach

The important question becomes:

Can we place all cows
such that minimum distance = X ?

If yes:

Try a larger distance

If no:

Try a smaller distance

This monotonic behaviour is perfect for Binary Search.

Pattern Recognition

Whenever you see:

Maximize Minimum
Minimum Distance
Feasibility Check

Think:

Binary Search on Answer

Key Observation

Suppose:

Distance = 3

and we can successfully place all cows.

Then:

Distance = 2
Distance = 1

will also work.

Similarly:

If distance 5 fails,

6
7
8

will also fail.

This creates a monotonic search space.

Optimal Approach

Step 1

Sort the stalls.

Arrays.sort(stalls);

Step 2

Binary Search on distance.

Search Space:

low = 1

high = stalls[n-1] - stalls[0]

Step 3

Check feasibility.

Place first cow at:

First Stall

Then greedily place every next cow at the first stall satisfying:

currentPosition - previousPosition >= distance

Optimal Java Solution

class Solution {

    public static int aggressiveCows(int[] stalls,
                                     int k) {

        Arrays.sort(stalls);

        int low = 1;

        int high =
            stalls[stalls.length - 1]
            - stalls[0];

        while (low <= high) {

            int mid =
                low + (high - low) / 2;

            if (canPlace(stalls, k, mid)) {

                low = mid + 1;

            } else {

                high = mid - 1;
            }
        }

        return high;
    }

    private static boolean canPlace(int[] stalls,
                                    int cows,
                                    int distance) {

        int count = 1;

        int lastPlaced = stalls[0];

        for (int i = 1;
             i < stalls.length;
             i++) {

            if (stalls[i] - lastPlaced >= distance) {

                count++;

                lastPlaced = stalls[i];
            }
        }

        return count >= cows;
    }
}

Dry Run

Input

stalls = [1,2,4,8,9]

k = 3

After Sorting:

1 2 4 8 9

Iteration 1

low = 1
high = 8

mid = 4

Try placing cows:

Cow 1 -> 1

Cow 2 -> 8

Need distance >= 4

Only:

2 cows placed

Not Possible.

Move Left.

high = 3

Iteration 2

mid = 2

Place:

1
4
8

3 cows placed.

Possible.

Try Bigger Distance

low = 3

Iteration 3

mid = 3

Place:

1
4
8

3 cows placed.

Possible.

low = 4

Loop Ends.

Answer

Maximum minimum distance.

Why Binary Search Works?

If:

Distance = 3

works,

then:

1
2

will definitely work.

If:

Distance = 5

fails,

then:

6
7
8

will also fail.

This monotonic property makes Binary Search possible.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N log(MaxDistance))
Space Complexity	O(1)

Interview One-Liner

Binary search the minimum distance and greedily check whether all cows can be placed while maintaining that distance.

Pattern Learned

Maximize Minimum
+
Feasibility Check

=> Binary Search on Answer

Memory Trick

Think:

Can I place all cows
with minimum distance X ?

YES
→ Try Bigger Distance

NO
→ Try Smaller Distance

Mental Model

Minimize Maximum
→ Allocate Pages

Maximize Minimum
→ Aggressive Cows

Whenever you hear:

"Maximum possible minimum distance"

your brain should immediately think:

Binary Search on Answer + Greedy Placement 🚀

Allocate Minimum Number of Pages | Binary Search on Answer

Jaspreet singh — Sun, 21 Jun 2026 16:23:42 +0000

geeksforgeeks.org

Problem Statement

Given:

books[i] = pages in ith book
m students

Allocate books such that:

Every student gets at least one book.
Books are allocated contiguously.
Every book is assigned.

Minimize:

Maximum pages assigned to any student

Return the minimum possible value.

Brute Force Intuition

In an interview, you can explain it like this:

Try every possible maximum page limit and check whether it is possible to distribute books among students while respecting that limit.

This works but is inefficient.

Complexity

Time Complexity: O(N × Sum)
Space Complexity: O(1)

Moving Towards the Optimal Approach

Think about the answer.

Minimum possible answer:

Maximum book pages

because one student must take that book.

Maximum possible answer:

Sum of all pages

when one student takes all books.

So answer lies in:

[max(book), sum(book)]

This screams:

Binary Search on Answer

Pattern Recognition

Whenever you see:

Minimize Maximum
Maximize Minimum
Feasibility Check

Think:

Binary Search on Answer

Key Observation

Suppose:

Maximum allowed pages = X

Can we allocate books to at most:

m students

If yes:

Try smaller answer

If no:

Need larger answer

Feasibility Function

For every book:

Add pages to current student

If limit exceeded:

Assign new student

Count students required.

Optimal Java Solution

class Solution {

    public int findPages(int[] arr,
                         int n,
                         int m) {

        if (m > n)
            return -1;

        int low = 0;
        int high = 0;

        for (int pages : arr) {

            low = Math.max(low, pages);
            high += pages;
        }

        while (low <= high) {

            int mid = low + (high - low) / 2;

            int students =
                countStudents(arr, mid);

            if (students > m) {

                low = mid + 1;

            } else {

                high = mid - 1;
            }
        }

        return low;
    }

    private int countStudents(int[] arr,
                              int maxPages) {

        int students = 1;
        int pages = 0;

        for (int book : arr) {

            if (pages + book <= maxPages) {

                pages += book;

            } else {

                students++;
                pages = book;
            }
        }

        return students;
    }
}

Dry Run

Input

books = [12,34,67,90]

students = 2

Search Space:

low = 90
high = 203

Iteration 1

mid = 146

Allocation:

12 + 34 + 67 = 113

Next 90 exceeds

Student 2 gets:

Students Needed:

Valid.

Try smaller answer.

Iteration 2

mid = 117

Students Needed:

Still valid.

Try smaller.

Eventually:

becomes answer.

Why Binary Search Works?

If:

113 pages works

Then:

will also work.

This monotonic behaviour allows Binary Search.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N × log(Sum))
Space Complexity	O(1)

Interview One-Liner

Binary search the maximum pages a student can receive and check if allocation is possible within m students.

Pattern Learned

Minimize Maximum
+
Feasibility Check

=> Binary Search on Answer

Memory Trick

Think:

Can all books be allocated
if no student gets
more than X pages?

YES
→ Try Smaller

NO
→ Increase X

Mental Model

Answer Exists in Range
        ↓
Check Feasibility
        ↓
Binary Search

Whenever you hear:

"Minimize the maximum"

your brain should immediately think:

Binary Search on Answer 🚀

kth smallest element in sorted array

Jaspreet singh — Sun, 21 Jun 2026 16:22:30 +0000

Problem Statement

Given two sorted arrays arr1[] and arr2[] and an integer k, return the kth smallest element from the combined sorted array.

Brute Force Intuition

In an interview, you can explain it like this:

Since both arrays are sorted, we can merge them similar to Merge Sort. While merging, keep counting elements. The moment we reach the kth element, return it.

Complexity

Time Complexity: O(N + M)
Space Complexity: O(N + M)

Brute Force Code

int[] merged = new int[n + m];

// Merge both arrays

return merged[k - 1];

Moving Towards the Optimal Approach

Notice something interesting:

For Median of Two Sorted Arrays, we partitioned arrays such that:

Left Half | Right Half

For Kth Element:

Exactly k elements must lie on the left side.

The partition idea remains exactly the same.

Pattern Recognition

Whenever you see:

Two Sorted Arrays
Kth Smallest Element
Logarithmic Solution Expected

Think:

Binary Search on Partition

Key Observation

Suppose:

arr1 = [2,3,6,7,9]
arr2 = [1,4,8,10]
k = 5

We need:

Exactly 5 elements on left side

Partition:

2 3 6 | 7 9

1 4   | 8 10

Left Side:

1 2 3 4 6

contains exactly:

5 elements

Answer becomes:

max(left1, left2)

Optimal Approach

Let:

cut1 = elements taken from arr1
cut2 = k - cut1

Valid partition requires:

left1 <= right2

left2 <= right1

Once valid:

answer = Math.max(left1, left2);

Optimal Java Solution

class Solution {

    public long kthElement(int k,
                           int arr1[],
                           int arr2[]) {

        int n1 = arr1.length;
        int n2 = arr2.length;

        if (n1 > n2)
            return kthElement(k, arr2, arr1);

        int low = Math.max(0, k - n2);
        int high = Math.min(k, n1);

        while (low <= high) {

            int cut1 = low + (high - low) / 2;

            int cut2 = k - cut1;

            int left1 =
                cut1 == 0 ? Integer.MIN_VALUE
                           : arr1[cut1 - 1];

            int left2 =
                cut2 == 0 ? Integer.MIN_VALUE
                           : arr2[cut2 - 1];

            int right1 =
                cut1 == n1 ? Integer.MAX_VALUE
                            : arr1[cut1];

            int right2 =
                cut2 == n2 ? Integer.MAX_VALUE
                            : arr2[cut2];

            if (left1 <= right2 &&
                left2 <= right1) {

                return Math.max(left1, left2);
            }

            else if (left1 > right2) {

                high = cut1 - 1;

            } else {

                low = cut1 + 1;
            }
        }

        return -1;
    }
}

Dry Run

Input

arr1 = [2,3,6,7,9]

arr2 = [1,4,8,10]

k = 5

Need:

5 elements on left side

Partition:

2 3 6 | 7 9

1 4   | 8 10

Check:

6 <= 8 ✓

4 <= 7 ✓

Valid Partition.

Answer:

max(6,4)

= 6

Why This Works?

The kth element is simply:

Largest element among the first k elements

When partition is valid:

Left side contains exactly k elements.

Hence:

max(left1, left2)

becomes the kth element.

Complexity Analysis

Metric	Complexity
Time Complexity	O(log(min(N,M)))
Space Complexity	O(1)

Interview One-Liner

Binary search the partition of the smaller array such that exactly k elements lie on the left side and both partitions remain sorted.

Pattern Learned

Two Sorted Arrays
+
Kth Element
+
Logarithmic Requirement

=> Binary Search on Partition

Memory Trick

Think:

Median Problem
=
Half Elements on Left

Kth Element Problem
=
Exactly K Elements on Left

Mental Model

Median of Two Arrays
→ Partition at Half

Kth Element
→ Partition at K

Once you solve Median of Two Sorted Arrays, this problem is almost the same with just one change:

Half → K

That's the entire trick. 🚀

Median of the two sorted arrays.

Jaspreet singh — Sun, 21 Jun 2026 16:21:29 +0000

Problem Statement

Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays.

The overall run time complexity should be:

O(log(min(N,M)))

Brute Force Intuition

In an interview, you can explain it like this:

Since both arrays are sorted, we can merge them into a single sorted array and then directly compute the median from the merged array.

Complexity

Time Complexity: O(N + M)
Space Complexity: O(N + M)

Brute Force Code

int[] merged = new int[n + m];

// Merge both arrays

return median;

Moving Towards the Optimal Approach

Do we really need the merged array?

No.

We only care about:

Left Half
Right Half

such that:

All elements in Left Half
<=
All elements in Right Half

This is where partition-based Binary Search comes in.

Pattern Recognition

Whenever you see:

Two Sorted Arrays
Median
O(log N) expected

Think:

Binary Search on Partition

Key Observation

For total elements:

n + m

Left partition should contain:

(n + m + 1) / 2

elements.

We Binary Search on:

How many elements to take from nums1

Remaining automatically come from nums2.

Optimal Java Solution

class Solution {

    public double findMedianSortedArrays(int[] nums1,
                                         int[] nums2) {

        if (nums1.length > nums2.length)
            return findMedianSortedArrays(nums2, nums1);

        int n1 = nums1.length;
        int n2 = nums2.length;

        int low = 0;
        int high = n1;

        while (low <= high) {

            int cut1 = low + (high - low) / 2;

            int cut2 =
                (n1 + n2 + 1) / 2 - cut1;

            int left1 =
                cut1 == 0 ? Integer.MIN_VALUE
                           : nums1[cut1 - 1];

            int left2 =
                cut2 == 0 ? Integer.MIN_VALUE
                           : nums2[cut2 - 1];

            int right1 =
                cut1 == n1 ? Integer.MAX_VALUE
                            : nums1[cut1];

            int right2 =
                cut2 == n2 ? Integer.MAX_VALUE
                            : nums2[cut2];

            if (left1 <= right2 &&
                left2 <= right1) {

                if ((n1 + n2) % 2 == 0) {

                    return (Math.max(left1, left2)
                          + Math.min(right1, right2))
                          / 2.0;
                }

                return Math.max(left1, left2);
            }

            else if (left1 > right2) {

                high = cut1 - 1;

            } else {

                low = cut1 + 1;
            }
        }

        return 0;
    }
}

Dry Run

Input

nums1 = [1,3]
nums2 = [2]

Total:

3 elements

Need:

2 elements on left side

Partition:

[1] | [3]

[2] |

Check:

left1 <= right2
left2 <= right1

Valid Partition.

Median:

max(1,2)
=
2

Complexity Analysis

Metric	Complexity
Time Complexity	O(log(min(N,M)))
Space Complexity	O(1)

Interview One-Liner

Binary search the partition of the smaller array and ensure all elements on the left side are less than or equal to all elements on the right side.

Pattern Learned

Two Sorted Arrays
+
Median
+
Logarithmic Requirement

=> Binary Search on Partition

Single Element in a Sorted Array

Jaspreet singh — Sat, 20 Jun 2026 17:45:50 +0000

leetcode.com

Problem Statement

Given a sorted array where:

Every element appears exactly twice.
Only one element appears once.

Find the single element in O(log N) time and O(1) space.

Brute Force Intuition

In an interview, you can explain it like this:

Since every element appears twice except one, we can iterate through the array and count frequencies. The element with frequency 1 is our answer. This works but doesn't utilize the sorted nature of the array.

Complexity

Time Complexity: O(N)
Space Complexity: O(1)

Brute Force Code

class Solution {

    public int singleNonDuplicate(int[] nums) {

        for (int i = 0; i < nums.length - 1; i += 2) {

            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }

        return nums[nums.length - 1];
    }
}

Moving Towards the Optimal Approach

The important observation is:

Before the single element:

Index: 0 1 2 3 4 5
Array: 1 1 2 2 3 3

Pairs start at EVEN indices.

After the single element:

Index: 0 1 2 3 4 5 6
Array: 1 1 2 3 3 4 4

Pairs start at ODD indices.

The single element breaks the pairing pattern.

This allows us to use Binary Search.

Pattern Recognition

Whenever you see:

Sorted Array
Pair Pattern
One Missing / One Unique Element

Think:

Binary Search on Index Pattern

Optimal Approach

Observation

If:

nums[mid] == nums[mid + 1]

then:

If mid is even → single element lies on right.
Otherwise → lies on left.

To simplify:

if(mid % 2 == 1)
    mid--;

Now every mid becomes even.

Optimal Java Solution

class Solution {

    public int singleNonDuplicate(int[] nums) {

        int low = 0;
        int high = nums.length - 1;

        while (low < high) {

            int mid = low + (high - low) / 2;

            if (mid % 2 == 1)
                mid--;

            if (nums[mid] == nums[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        }

        return nums[low];
    }
}

Dry Run

Input

nums = [1,1,2,2,3,4,4]

Iteration 1

low = 0
high = 6

mid = 3
mid = 2 (make even)

nums[2] = 2
nums[3] = 2

Pair exists.

Move Right

low = 4

Iteration 2

low = 4
high = 6

mid = 5
mid = 4

nums[4] = 3
nums[5] = 4

Pair broken.

Move Left

high = 4

Result

low = high = 4

Answer = 3

Why This Works?

Before the single element:

Pair starts at Even Index

After the single element:

Pair starts at Odd Index

Binary Search helps identify where this pattern breaks.

Complexity Analysis

Metric	Complexity
Time Complexity	O(log N)
Space Complexity	O(1)

Interview One-Liner

In a sorted array, pairs start at even indices before the single element and at odd indices after it. Binary search on this pattern finds the answer in O(log N).

Pattern Learned

Sorted Array
+
Pair Structure
+
One Unique Element

=> Binary Search on Index Pattern

Search in Rotated Sorted Array | Modified Binary Search

Jaspreet singh — Sat, 20 Jun 2026 17:45:01 +0000

leetcode.com

Problem Statement

Given a rotated sorted array nums and an integer target, return the index of target.

If the target does not exist, return -1.

You must solve it in:

O(log N)

time.

Brute Force Intuition

In an interview, you can explain it like this:

We can scan the array from left to right and compare every element with the target. As soon as we find the target, we return its index. This works but does not utilize the sorted nature of the array.

Complexity

Time Complexity: O(N)
Space Complexity: O(1)

Brute Force Code

class Solution {

    public int search(int[] nums, int target) {

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] == target)
                return i;
        }

        return -1;
    }
}

Moving Towards the Optimal Approach

A normal Binary Search works only when the array is completely sorted.

But after rotation:

[4,5,6,7,0,1,2]

the entire array is not sorted.

However, one important property still remains:

At least one half is always sorted.

This observation allows us to eliminate half of the search space every time.

Pattern Recognition

Whenever you see:

Sorted Array
Rotation
Search Target

Think:

Modified Binary Search

Key Observation

For any mid:

[4,5,6 | 7 | 0,1,2]

One side will always be sorted.

Either:

Left Half Sorted

Right Half Sorted

Once we identify the sorted half, we check whether the target lies inside it.

Optimal Approach

Case 1

Left Half Sorted

if(nums[low] <= nums[mid])

Example:

4 5 6 7

If target lies within:

nums[low] <= target < nums[mid]

Search left.

Otherwise search right.

Case 2

Right Half Sorted

else

Example:

0 1 2

If target lies within:

nums[mid] < target <= nums[high]

Search right.

Otherwise search left.

Optimal Java Solution

class Solution {

    public int search(int[] arr, int target) {

        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            if (arr[mid] == target)
                return mid;

            if (arr[low] <= arr[mid]) {

                if (arr[low] <= target &&
                    target < arr[mid]) {

                    high = mid - 1;

                } else {

                    low = mid + 1;
                }

            } else {

                if (arr[mid] < target &&
                    target <= arr[high]) {

                    low = mid + 1;

                } else {

                    high = mid - 1;
                }
            }
        }

        return -1;
    }
}

Dry Run

Input

nums = [4,5,6,7,0,1,2]
target = 0

Iteration 1

low = 0
high = 6

mid = 3
nums[mid] = 7

Left side:

4 5 6 7

is sorted.

Check:

0 lies between 4 and 7 ?

No.

Move Right.

low = 4

Iteration 2

low = 4
high = 6

mid = 5
nums[mid] = 1

Left side:

0 1

is sorted.

Check:

0 lies between 0 and 1 ?

Yes.

Move Left.

high = 4

Iteration 3

low = 4
high = 4

mid = 4
nums[mid] = 0

Found Target ✅

Answer = 4

Why This Works?

Even though the array is rotated:

One half always remains sorted.

Using that sorted half, we can determine whether the target can exist there.

This allows us to eliminate half the search space every iteration.

Complexity Analysis

Metric	Complexity
Time Complexity	O(log N)
Space Complexity	O(1)

Interview One-Liner

In a rotated sorted array, at least one half is always sorted. Identify the sorted half and decide whether the target lies inside it to eliminate half the search space.

Pattern Learned

Sorted Array
+
Rotation
+
Search

=> Modified Binary Search

Memory Trick

Think:

Find Sorted Half
        ↓
Target Inside ?
        ↓
Yes → Go There
No  → Go Other Half

Mental Model

Normal Binary Search
→ Array Fully Sorted

Rotated Binary Search
→ One Half Sorted

Whenever you hear:

"Search in Rotated Sorted Array"

your brain should immediately think:

Find Sorted Half → Check Target Range → Eliminate Half

Median in a Row Wise Sorted Matrix | Binary Search on Answer

Jaspreet singh — Sat, 20 Jun 2026 17:43:48 +0000

geeksforgeeks.org

Problem Statement

Given a row-wise sorted matrix of size N × M, find the median of the matrix.

The matrix contains an odd number of elements.

Brute Force Intuition

In an interview, you can explain it like this:

Since every row is sorted, one straightforward approach is to collect all elements into a single array, sort them, and return the middle element. This works but ignores the fact that rows are already sorted.

Complexity

Time Complexity: O(N × M × log(N × M))
Space Complexity: O(N × M)

Brute Force Code

class Solution {

    public int median(int[][] mat) {

        List<Integer> list = new ArrayList<>();

        for (int[] row : mat) {

            for (int num : row) {
                list.add(num);
            }
        }

        Collections.sort(list);

        return list.get(list.size() / 2);
    }
}

Moving Towards the Optimal Approach

Notice that we don't actually need the sorted array.

We only need:

How many numbers are smaller than or equal to X?

If we can answer this efficiently, we can binary search the median value.

Pattern Recognition

Whenever you see:

Sorted Rows
Find kth smallest / median
Value range known

Think:

Binary Search on Answer

Key Observation

Suppose:

mid = 10

Count:

How many elements ≤ 10 ?

If that count is:

Too small

Median lies on the right.

If count is:

Large enough

Median lies on the left.

Why Upper Bound?

Each row is sorted.

For every row we can find:

Count of elements ≤ mid

using Binary Search.

This takes:

O(log M)

per row.

Optimal Java Solution

class Solution {

    public int median(int[][] mat) {

        int n = mat.length;
        int m = mat[0].length;

        int low = 1;
        int high = 2000;

        int required = (n * m) / 2;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            int count = 0;

            for (int[] row : mat) {
                count += upperBound(row, mid);
            }

            if (count <= required) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return low;
    }

    private int upperBound(int[] row, int target) {

        int low = 0;
        int high = row.length - 1;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            if (row[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return low;
    }
}

Dry Run

Input

1  3  5
2  6  9
3  6  9

Total Elements:

Median Position:

9 / 2 = 4

Need the 5th smallest element.

Iteration 1

mid = 5

Count elements ≤ 5:

Row1 → 3
Row2 → 1
Row3 → 1

Total = 5

Since:

5 > 4

Move Left.

Iteration 2

mid = 3

Count elements ≤ 3:

Row1 → 2
Row2 → 1
Row3 → 1

Total = 4

Since:

4 <= 4

Move Right.

Result

Median = 5

Why Binary Search Works?

We are not searching indices.

We are searching values.

For every value:

Count(elements ≤ value)

This count grows monotonically.

Hence Binary Search becomes possible.

Complexity Analysis

Metric	Complexity
Time Complexity	O(log(MaxValue) × N × log M)
Space Complexity	O(1)

Where:

log(MaxValue) → Binary Search on answer.
log(M) → Upper Bound in each row.

Interview One-Liner

Binary search the value range and count how many elements are ≤ mid using upper bound on every sorted row.

Pattern Learned

Sorted Structure
+
Need kth Smallest / Median
+
Monotonic Count

=> Binary Search on Answer

Memory Trick

Think:

Guess a Number (mid)

Count:
How many elements ≤ mid ?

Count Too Small
→ Move Right

Count Large Enough
→ Move Left

Mental Model

Binary Search on Index
→ Search Position

Binary Search on Answer
→ Search Value

Whenever you hear:

"Median in Sorted Matrix"

your brain should immediately think:

Count Elements ≤ Mid + Binary Search on Answer

N-th root of a number | Binary Search on Answer

Jaspreet singh — Sat, 20 Jun 2026 17:42:30 +0000

N-th root of a number - GeeksforGeeks

Your All-in-One Learning Portal: GeeksforGeeks is a comprehensive educational platform that empowers learners across domains-spanning computer science and programming, school education, upskilling, commerce, software tools, competitive exams, and more.

geeksforgeeks.org

Problem Statement

Given two integers:

n → root value
m → number

Find the integer x such that:

xⁿ = m

Return:

if it exists, otherwise return:

-1

Brute Force Intuition

In an interview, you can explain it like this:

We can try every number from 1 to m and calculate its nth power. If any number's nth power becomes equal to m, we have found our answer. Although straightforward, it unnecessarily checks many values.

Complexity

Time Complexity: O(M × N)
Space Complexity: O(1)

Brute Force Code

class Solution {

    public int nthRoot(int n, int m) {

        for (int i = 1; i <= m; i++) {

            long value = 1;

            for (int j = 0; j < n; j++) {
                value *= i;
            }

            if (value == m)
                return i;
        }

        return -1;
    }
}

Moving Towards the Optimal Approach

Notice:

If midⁿ < m

then the answer must lie on the right.

And if:

midⁿ > m

the answer must lie on the left.

This is exactly the Binary Search pattern.

Instead of searching indices, we are searching the answer itself.

Pattern Recognition

Whenever you see:

Find minimum/maximum possible answer
Answer lies in a range
Monotonic behaviour

Think:

Binary Search on Answer

Optimal Approach

Search in the range:

[1, m]

For every middle value:

midⁿ

Compare with:

Cases:

midⁿ == m → Found Answer

midⁿ < m  → Search Right

midⁿ > m  → Search Left

Optimal Java Solution

class Solution {

    public int nthRoot(int n, int m) {

        int low = 1;
        int high = m;

        while (low <= high) {

            int mid = low + (high - low) / 2;

            long value = power(mid, n);

            if (value == m)
                return mid;

            if (value < m)
                low = mid + 1;
            else
                high = mid - 1;
        }

        return -1;
    }

    private long power(long base, int n) {

        long ans = 1;

        for (int i = 0; i < n; i++) {

            ans *= base;

            if (ans > Integer.MAX_VALUE)
                return ans;
        }

        return ans;
    }
}

Dry Run

Input

n = 3
m = 27

Iteration 1

low = 1
high = 27

mid = 14

14³ = 2744

2744 > 27

Move Left

Iteration 2

low = 1
high = 13

mid = 7

7³ = 343

343 > 27

Move Left

Iteration 3

low = 1
high = 6

mid = 3

3³ = 27

Found Answer ✅

Why Binary Search Works?

The function:

f(x) = xⁿ

is monotonic increasing.

That means:

If x increases,
xⁿ also increases.

So we can safely eliminate half of the search space every time.

Complexity Analysis

Metric	Complexity
Time Complexity	O(log M × N)
Space Complexity	O(1)

Where:

log M comes from Binary Search.
N comes from calculating midⁿ.

Interview One-Liner

Since xⁿ increases monotonically with x, we can binary search the answer space and compare midⁿ with m.

Pattern Learned

Answer Lies in a Range
+
Monotonic Function

=> Binary Search on Answer

Memory Trick

Think:

midⁿ

Less than m ?
→ Go Right

Greater than m ?
→ Go Left

Equal ?
→ Answer Found

Mental Model

Sorted Array
→ Binary Search on Index

Nth Root
→ Binary Search on Answer

Whenever you hear:

"Find an exact root"

your brain should immediately think:

Binary Search on Answer Space

HLD Fundamentals #6 : Consistent Hashing: The Smart Way to Scale Distributed Systems

Jaspreet singh — Sat, 20 Jun 2026 11:54:16 +0000

Consistent Hashing Explained: The Smart Way to Scale Distributed Systems

Most system design interviews eventually reach a point where the interviewer asks:

"What happens when a new server is added?"

At first, scaling sounds easy—just add another machine.

But in distributed systems, adding or removing servers can cause massive data movement, cache misses, and performance degradation if data distribution isn't handled correctly.

This is exactly the problem Consistent Hashing solves.

It is one of the most important concepts behind systems like Amazon DynamoDB, Cassandra, Redis Cluster, Memcached, Akamai CDN, and many large-scale distributed databases.

In this article, we'll understand:

Why Consistent Hashing exists
Problems with traditional hashing
How Consistent Hashing works
Virtual Nodes
Real-world use cases
Interview-focused explanations

Why Do We Need Consistent Hashing?

Imagine you have:

3 cache servers
Millions of user sessions
Data distributed across servers

A simple approach would be:

Server = Hash(Key) % NumberOfServers

Example:

Hash(User123) % 3 = Server 1
Hash(User456) % 3 = Server 2
Hash(User789) % 3 = Server 0

This works perfectly...

Until your traffic increases.

Now you add a fourth server.

Server = Hash(Key) % 4

Suddenly almost every key gets remapped.

The Big Problem

Before:

Hash(User123) % 3 = Server 1

After adding Server 4:

Hash(User123) % 4 = Server 3

The same user now points to a completely different server.

As a result:

Cache becomes useless
Data must be migrated
Massive cache misses occur
System performance drops

This process is called Rebalancing.

The Rebalancing Problem

Suppose you have:

100 Million Records
3 Servers

You add a new server.

With modulo-based hashing:

Almost all records need redistribution

That's extremely expensive.

For large-scale systems:

Data transfer takes time
Network bandwidth increases
Cache hit ratio drops
User latency increases

We need a better solution.

Enter Consistent Hashing

Consistent Hashing is a technique designed to minimize data movement when servers are added or removed.

Main Goal

Instead of moving all data:

Move only a small portion of data

In a properly balanced system:

Only 1/N of keys are reassigned

Where:

N = Number of Servers

This makes scaling significantly cheaper.

Core Idea: The Hash Ring

Unlike normal hashing, Consistent Hashing places both:

Servers
Data Keys

on a virtual circular ring.

Step 1: Create a Ring

Imagine a hash space:

0 → 360°

0 → 2^32 - 1

Both servers and keys are hashed into this space.

Example:

Server A → 50
Server B → 150
Server C → 300

Ring:

          0
       /     \
    300       50
       \     /
        150

Step 2: Place Keys on the Ring

Suppose:

User1 → 70
User2 → 180
User3 → 320

Now each key searches clockwise for the next available server.

Data Assignment Rule

A key belongs to:

The first server encountered while moving clockwise.

Example:

User1 → 70

Clockwise:

70 → Server B(150)

Assigned to:

Server B

Another Example

User2 → 180

Clockwise:

180 → Server C(300)

Assigned to:

Server C

Another Example

User3 → 320

Clockwise:

320 → wrap around → Server A(50)

Assigned to:

Server A

This wrapping behavior is why it's called a ring.

What Happens When a New Server Is Added?

Suppose a new server appears:

Server D → 220

Before:

Server B(150) → Server C(300)

After:

Server B(150) → Server D(220) → Server C(300)

Only keys between:

150 and 220

move to Server D.

Everything else remains untouched.

Result

Instead of moving:

100% of data

We move roughly:

1/N of data

This is the biggest advantage of Consistent Hashing.

What Happens When a Server Fails?

Suppose:

Server B crashes

Only the keys owned by Server B need reassignment.

Those keys move to the next clockwise server.

Example:

Server B → Down

Keys automatically move to:

Server C

The rest of the ring remains unchanged.

This makes Consistent Hashing naturally fault tolerant.

The Uneven Distribution Problem

There is still one issue.

Suppose servers are placed like:

Server A → 10
Server B → 15
Server C → 250

Now Server C owns a huge portion of the ring.

Result:

Uneven Load Distribution

Some servers become overloaded while others sit idle.

Virtual Nodes (VNodes)

To solve uneven distribution, we use Virtual Nodes.

Instead of placing a server once:

Server A → 50

Place it multiple times:

Server A-1 → 50
Server A-2 → 120
Server A-3 → 280

Similarly:

Server B-1
Server B-2
Server B-3

Server C-1
Server C-2
Server C-3

Now the ring becomes much more balanced.

Why Virtual Nodes Matter

Better Load Balancing

Requests spread more evenly.

Easier Scaling

Adding a new machine impacts smaller portions of the ring.

Better Fault Tolerance

Failure impact is distributed across the cluster.

Real-World Example: Redis Cluster

Imagine:

5 Redis Nodes

User sessions are stored using Consistent Hashing.

When traffic grows:

Add Redis Node 6

Without Consistent Hashing:

Almost entire cache gets reshuffled

With Consistent Hashing:

Only a small subset of keys move

Cache hit rate remains high.

System stays stable.

Real-World Example: Database Sharding

Suppose Amazon stores customer data across many database shards.

Customer IDs are hashed onto a ring.

When storage grows:

Add New Shard

Only nearby data migrates.

No massive rebalancing operation is required.

Advantages vs Disadvantages

Advantages	Disadvantages
Minimal data movement	More complex than modulo hashing
Easy horizontal scaling	Requires hash ring management
High cache hit ratio	Virtual nodes add implementation complexity
Fault tolerant	Debugging can be harder
Widely used in distributed systems	Uneven distribution without VNodes

Interview Questions You Should Be Ready For

Why not use modulo hashing?

Because adding or removing a server changes the modulo value, causing almost all keys to be remapped.

What problem does Consistent Hashing solve?

It minimizes rebalancing when servers are added or removed.

How are keys assigned?

A key is assigned to the first server encountered in the clockwise direction on the hash ring.

What are Virtual Nodes?

Multiple logical representations of the same physical server placed on the ring to improve load distribution.

How much data moves when a server is added?

Approximately:

1/N of the total data

instead of almost all data.

Interview Answer in 60 Seconds

Consistent Hashing is a data distribution technique used in distributed systems to minimize rebalancing when servers are added or removed. Instead of using Hash(Key) % N, both servers and keys are placed on a virtual hash ring. A key is assigned to the next server in the clockwise direction. When a server joins or leaves, only a small subset of keys is reassigned, typically around 1/N of the total data. To ensure even distribution, Virtual Nodes are used, where each physical server is represented multiple times on the ring. It is commonly used in Redis, Cassandra, DynamoDB, Memcached, and large-scale sharded databases.

TL;DR

Traditional hashing uses Hash(Key) % N
Adding/removing servers causes massive rebalancing
Consistent Hashing uses a virtual ring
Keys move clockwise to the nearest server
Only ~1/N of data moves during scaling
Virtual Nodes solve uneven distribution
Used in Redis, Cassandra, DynamoDB, Memcached, CDNs, and database sharding
One of the most frequently asked distributed systems interview topics

Scaling isn't just about adding servers.

The real challenge is adding servers without moving everything.

That's exactly why Consistent Hashing became a foundational building block of modern distributed systems.

Have you ever implemented Consistent Hashing in a real project, or only discussed it in interviews? Share your experience in the comments.

DEV Community: Jaspreet singh

Implement a Max Heap

Problem Statement

Intuition

Java Implementation

Dry Run

Complexity Analysis

Interview One-Liner

Pattern Learned

Maximum Sum Combinations

Problem Statement

Brute Force Intuition

Complexity

Brute Force Code

Better Approach (Your Code)

Complexity

Moving Towards Optimal

Optimal Complexity

Interview One-Liner

Pattern Learned

Kth Largest Element | Heaps

Problem Statement

Brute Force Intuition

Complexity

Brute Force Code

Moving Towards the Better Heap Approach

Pattern Recognition

Better Approach

Optimal Java Solution

Dry Run

Input

Complexity Analysis

Interview One-Liner

Pattern Learned

Aggressive Cows

Problem Statement

Brute Force Intuition

Complexity

Brute Force Code

Moving Towards the Optimal Approach

Pattern Recognition

Key Observation

Optimal Approach

Step 1

Step 2

Step 3

Optimal Java Solution

Dry Run

Input

Iteration 1

Iteration 2

Iteration 3

Answer

Why Binary Search Works?

Complexity Analysis

Interview One-Liner

Pattern Learned

Similar Problems

Memory Trick

Mental Model

Allocate Minimum Number of Pages | Binary Search on Answer

Problem Statement

Brute Force Intuition

Complexity

Moving Towards the Optimal Approach

Pattern Recognition

Key Observation

Feasibility Function

Optimal Java Solution

Dry Run

Input

Iteration 1

Iteration 2

Why Binary Search Works?

Complexity Analysis

Interview One-Liner

Pattern Learned

Similar Problems

Memory Trick

Mental Model