Forem: we_are_broken_compilers

Largest Subarray with 0 sum

we_are_broken_compilers — Tue, 21 Apr 2026 09:09:39 +0000

Problem Statement

Given an array of integers, find the maximum length of a subarray whose sum is 0.

Example

Input:
arr = [15, -2, 2, -8, 1, 7, 10, 23]

Output:
5

Explanation:

The longest subarray with sum 0 is:
[-2, 2, -8, 1, 7]

First Approach (Brute Force)

The first idea that comes to mind is:

Fix a starting index i
Keep adding elements till index j
Check if the sum becomes 0
Track the maximum length

Code (Java – Brute Force)

class Solution {
    int maxLength(int arr[]) {
        int maxLen = 0;

        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];

                if (sum == 0) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }
        return maxLen;
    }
}

Problem with this approach

Time Complexity: O(n²)

For large inputs, this may cause TLE (Time Limit Exceeded)

Optimized Approach (Prefix Sum + HashMap)

Main Idea : If the same prefix sum appears again,
then the subarray between those two indices has sum 0.

Why?

prefixSum[j] - prefixSum[i] = 0
prefixSum[j] == prefixSum[i]

Here prefixSum[j] is the sum of elements from 0 to j and prefixSum[i] is the sum of elements from 0 to i
If both are same then ,The sum of elements between i+1 and j becomes zero

Why HashMap?

Because we need to:

Store prefix sum

Along with its first occurrence index

Optimized Code (Java – O(n))

class Solution {
    int maxLength(int arr[]) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1); // to handle subarray starting from index 0

        int sum = 0;
        int maxLen = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];

            if (map.containsKey(sum)) {
                maxLen = Math.max(maxLen, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }
        return maxLen;
    }
}

Why do we store (0, -1) initially?

This handles the edge case when the subarray starts from index 0.

Example:

arr = [1, -1]
prefix sum at index 1 = 0
length = 1 - (-1) = 2

So -1 represents a virtual index before the array starts.

Complexity Analysis

Time Complexity :O(n)
We traverse the array only once.

Space Complexity : O(n)
Due to HashMap storing prefix sums.

So this is all about this problem
If you found this solution even a bit worst
Please make sure to hit like button and also share it your coding fellows

Koko Eating Banana

we_are_broken_compilers — Mon, 20 Apr 2026 14:37:27 +0000

So by reading the heading, what comes to your mind?

Someone named Koko is eating bananas, right?
Exactly — and the problem statement is pretty much about that.

The problem says there is a monkey named Koko who loves to eat bananas. We are given an array of banana piles, where each element represents the number of bananas in a pile.

Our task is to find the minimum number of bananas Koko should eat per hour so that she can finish all the bananas within k hours.

First Thought on Reading the Problem

Once you read the problem, what does it remind you of?

Something we’ve already done before, right?
Minimum Time to Complete Trips

So the first advice is:
Try to attempt the problem yourself before jumping to the solution.

Key Observation

If you look closely, this is a monotonic problem:

If Koko can eat all bananas at speed x
then she can also eat all bananas at any speed greater than x.

This monotonic behavior immediately hints toward Binary Search on the Answer.

The problem is very similar to Minimum Time to Complete Trips, with just a few extra checks and a small formula adjustment.

Solution Approach

Binary Search Boundaries

Lower bound (lb) = 1 → Because Koko can eat at least one banana per hour
Upper bound (ub) = maxPile → At most, she eats the largest pile in one hour

Binary Search Process

Compute mid as a candidate eating speed
Check if it is possible to eat all bananas at this speed within k hours

Decision Making

* If it **is possible**:

 -  Reduce the upper bound: `ub = mid`
 -  Because *“Itne mein toh ho hi jaega”*
   -> Now search for a better (smaller) speed

If it is not possible:
- Increase the lower bound: lb = mid + 1
- So that Koko eats a bit more bananas per hour

Feasibility Check Logic

For each pile:

Calculate how many full hours are needed using division
If some bananas remain, add one extra hour
Keep accumulating total time
If at any point time > k, return false immediately

Code (Java)

class Solution {
    public static boolean isPossible(int[] piles, int bananaAte, int k) {
        int time = 0;

        for (int pile : piles) {
            time += pile / bananaAte;

            if (pile % bananaAte != 0) {
                time++;
            }

            if (time > k) return false;
        }
        return true;
    }

    public int kokoEat(int[] arr, int k) {
        int max = Integer.MIN_VALUE;
        for (int val : arr) {
            max = Math.max(val, max);
        }

        int l = 1;
        int r = max;

        while (l < r) {
            int mid = l + (r - l) / 2;

            if (isPossible(arr, mid, k)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

Time Complexity

Time Complexity: `O(n log maxPile)`

Explanation:
Let:

n = number of piles
maxPile = maximum bananas in a pile

Binary Search

Search space: 1 → maxPile
Time taken: O(log maxPile)

Feasibility Check (`isPossible`)

Traverses all piles
Time taken: O(n)

Total

O(n log maxPile)

Space Complexity

Space Complexity: `O(1)`

No extra data structures used
Only a few variables

Final Words

So that’s all about the Koko Eating Bananas problem

If you’re still reading my blog till here —
Thank you so much, buddy!
Please make sure to share it with your code fellows.

Happy Coding!!

If you want, I can also:

make it more beginner-friendly
shorten it for LinkedIn/LeetCode discussion
or add visual examples for better intuition

Minimum Time to Complete Trips

we_are_broken_compilers — Tue, 03 Feb 2026 14:00:46 +0000

Hey fellow developers 👋

Welcome back to our DSA learning series!

In this series, we focus on problems that may look simple at first, but often require deeper thinking to solve efficiently. We are learning DSA just like you, so our goal is always to build intuition first — before jumping into code.

In this post, we are going to explore a problem that teaches you an important concept called Binary Search on Answer — Minimum Time to Complete Trips.

Problem Statement

We are given an array time[], where time[i] represents how much time the i-th bus takes to complete one trip.

Our goal is to find the minimum time required to complete totalTrips trips when all buses are working in parallel.

Understanding the Idea

Each bus keeps running continuously.

So, in a given time T:

A bus with time t can complete T / t trips
All buses together can complete the sum of these trips

Our task is to find the smallest time T for which total trips ≥ totalTrips.

Brute Force Approach

Idea

Start checking from time T = 1
For each T, calculate how many trips all buses can complete
Stop when trips ≥ required trips

Brute Force Code (Java)

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long T = 1;

        while (true) {
            long trips = 0;
            for (int t : time) {
                trips += T / t; // trips by this bus in T time
            }

            if (trips >= totalTrips) return T;
            T++;
        }
    }
}

Why `trips += T / t` Works

If:

time[i] = 3
T = 6

Then:

6 / 3 = 2 trips

So dividing time gives us the number of trips completed.

Complexity (Brute Force)

Time Complexity: O(n × ans)

n → number of buses
ans → minimum required time

Since ans can be very large, this approach will TLE for big inputs.

Space Complexity: O(1)

Optimal Approach (Binary Search on Answer)

Instead of checking every time value, we can search the answer efficiently using binary search.

Key Observation

Time is monotonic:

If we can finish in T time
Then we can also finish in T + 1, T + 2, ...

So binary search is possible on time.

Search Space

Lower Bound (lb) = 1
Upper Bound (ub) = min(time) × totalTrips

Why?

Because in the worst case, the fastest bus does all trips alone.

Binary Search Logic

Find mid
Check if we can finish totalTrips in mid time
If yes → try smaller time
If no → increase time

When lb == ub, we get our answer.

Optimal Code (Java)

class Solution {

    public static boolean isAtleast(int[] time, long givenTime, int totalTrips) {
        long trips = 0;

        for (int t : time) {
            trips += givenTime / t;
            if (trips >= totalTrips) return true;
        }

        return false;
    }

    public long minimumTime(int[] time, int totalTrips) {

        int min = Integer.MAX_VALUE;
        for (int t : time) {
            min = Math.min(min, t);
        }

        long lb = 1;
        long ub = (long) min * totalTrips;

        while (lb < ub) {
            long mid = lb + (ub - lb) / 2;

            if (isAtleast(time, mid, totalTrips)) {
                ub = mid;
            } else {
                lb = mid + 1;
            }
        }

        return lb;
    }
}

Complexity (Optimal)

Time Complexity: O(n log(totalTrips))

Why?

Binary search on answer space
Each step takes O(n) to check feasibility

So:

O(n × log(searchSpace))
≈ O(n log(totalTrips))

Space Complexity: O(1)

Final Thoughts

This problem is a classic example of Binary Search on Answer.

Once you learn to recognize patterns like:

false false false true true true

Binary search becomes a powerful tool in your DSA journey.

If you read till here — thank you so much!

If you found this helpful, please like and share it with your coding friends to help us build a stronger community.

Minimum Rounds to Complete All Tasks

we_are_broken_compilers — Sun, 25 Jan 2026 12:27:00 +0000

Hey fellow developers 👋

Welcome back to our DSA learning series!

In this series, we focus on problems that look simple at first but often confuse beginners because of tricky constraints and edge cases. We are learning DSA just like you, so the goal is always to break problems down logically instead of jumping straight into the code.

In this post, we are going to discuss a greedy-based problem that helps you understand how frequency counting and optimal grouping work together to minimize operations.

Task Rules

In one round, you can complete either 2 or 3 tasks of the same difficulty
You must complete all tasks
If it’s not possible (for example, only one task of a difficulty is left), return -1

Example
Input
tasks = [2,2,3,3,2,4,4,4,4,4]

Explanation

We can complete the tasks in the following way:

Round 1 → 3 tasks of difficulty 2
Round 2 → 2 tasks of difficulty 3
Round 3 → 3 tasks of difficulty 4
Round 4 → 2 tasks of difficulty 4

So the minimum number of rounds required is 4.

Approach (Greedy + HashMap)

Since we need to group tasks by difficulty, the first thing that comes to mind is a HashMap.

Step 1: Count frequency of each difficulty

Store:

difficulty (key)→ number of occurrences (Count)

Step 2: Calculate rounds for each difficulty

For each difficulty count:

If count == 1 → ❌ not possible → return -1
If count % 3 == 0 → use all groups of 3

Otherwise → use as many groups of 3 as possible and one group of 2

Why this works?

A group of 3 is more efficient than 2 (fewer rounds)

For any remainder:

4 = 2 + 2
5 = 3 + 2
8 = 3 + 3 + 2 So we just add one extra round when it's not divisible by 3.

Code (Java)

class Solution {
    public int minimumRounds(int[] tasks) {
        HashMap<Integer, Integer> mp = new HashMap<>();

        // Count frequency of each difficulty
        for (int task : tasks) {
            mp.put(task, mp.getOrDefault(task, 0) + 1);
        }

        int rounds = 0;

        // Calculate rounds
        for (int key : mp.keySet()) {
            int count = mp.get(key);

            if (count == 1) {
                return -1;
            }

            if (count % 3 == 0) {
                rounds += count / 3;
            } else {
                rounds += (count / 3) + 1;
            }
        }

        return rounds;
    }
}

Complexity Analysis

Time Complexity: O(n)

One loop to build the HashMap → O(n)
One loop over unique difficulties → at most O(n)
HashMap operations (get, put) are O(1) on average

Overall: O(n)

Space Complexity: O(n)

HashMap stores frequencies of tasks

Why Time Complexity Is Linear?

Because:

Each task is processed once
HashMap operations take constant time
No nested loops

So total operations grow linearly with input size.

If you found this helpful, give it a like 👍 and share it with your fellow coders!
Happy coding !!!

Delete a Node in a Binary Search Tree (BST)

we_are_broken_compilers — Wed, 31 Dec 2025 17:34:36 +0000

Hey fellow developers 👋

Welcome back to our DSA learning series!

This series is all about picking problems that every beginner finds confusing at first — and breaking them down slowly and logically. We are students ourselves, and we know how overwhelming DSA can feel if you jump straight into the code without understanding why something works.

In this post, we are going to talk about a problem that really helps you understand how Binary Search Trees work beneath the surface:

Deleting a node from a Binary Search Tree (BST).

At first, it may feel a bit complicated — especially when the node has children.
But once you slow down and reason through each case, the logic becomes surprisingly neat and structured.

Let us walk through it step by step.

Quick Reminder: What Makes a BST Special?

In a Binary Search Tree:

All values in the left subtree are smaller than the node
All values in the right subtree are greater

This ordering is exactly what allows us to efficiently search, insert, and delete.

Problem Statement

You are given the root of a BST and a value key.
Your job is to delete the node with that key (if it exists) and return the updated tree.

The twist: Deletion must be handled in a way that keeps the tree a valid BST.

Finding the Node First

Before deleting anything, we first locate the node:

If key < root.val → go left
If key > root.val → go right
If equal → this is the node we want to delete

The Three Deletion Cases

Once we find the node, there are only three possible scenarios.

Case 1: Node Has No Children (Leaf Node)

This is the easiest case. If the node has no left and right child, we simply remove it.
return null;

Case 2: Node Has One Child

If the node has only one child, we replace it with that child.

Only right child → return root.right
Only left child → return root.left

Case 3: Node Has Two Children (The Interesting One)

This is where most students get stuck — but it follows a very clean idea. We cannot just delete the node, because both sides still hold valid subtrees.

So we do this:

Find the inorder successor (the smallest value in the right subtree).
Copy its value into the current node.
Delete that successor node from the right subtree.

Putting It All Together — Code

class Solution {

    // finds the inorder successor (smallest node in right subtree)
    public static TreeNode inOrderSuccessor(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return root;

        // searching for the node
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } 
        else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } 
        else {
            // found
            // Case 1: no children
            if (root.left == null && root.right == null) {
                return null;
            }

            // Case 2: one child
            if (root.left == null) {
                return root.right;
            } 
            else if (root.right == null) {
                return root.left;
            }

            // Case 3: two children
            TreeNode successor = inOrderSuccessor(root.right);
            root.val = successor.val;
            root.right = deleteNode(root.right, successor.val);
        }

        return root;
    }
}

Final Thoughts

What makes this problem powerful is not the code — it is the structured way of thinking:

Understand the BST property
Identify the node
Handle each deletion case calmly
Preserve the structure

Once this mental model clicks, most tree problems suddenly feel more manageable.

If you try implementing this yourself a couple of times, you will notice the logic becoming second nature.

Happy coding — and see you in the next article!

Next Permutation — Intuition, Explanation, and Clean Implementation

we_are_broken_compilers — Thu, 11 Dec 2025 11:53:26 +0000

Hey fellow developers 👋

Welcome back to our DSA learning series!

This series is all about picking problems that every beginner finds confusing at first — and breaking them down slowly, logically, and humanly. We are students ourselves, and we know how overwhelming DSA can feel if you jump straight into the code without understanding why something works.

Today, we are exploring a classic problem that helps build strong intuition around arrays and ordering — Next Permutation.

At first glance, it feels abstract and mathematical.

But once you understand the pattern behind permutations, the entire logic becomes surprisingly simple and elegant.

Problem Statement

We are given an array of integers representing a permutation.

Our goal is to rearrange the numbers to form the next lexicographically greater permutation.

If such an arrangement does not exist (meaning the array is already the highest possible permutation), we return the lowest possible arrangement — which is just the array sorted in ascending order.

Example:

[1,2,3] → [1,3,2]
[2,3,1] → [3,1,2]
[3,2,1] → [1,2,3]

The rearrangement must be in-place and use constant extra memory.

Understanding the Core Idea

Before we try to code anything, let us think about what it means for one permutation to come after another in lexicographical order.

Take this example:

1 2 5 4 3

We want to find the "next" arrangement.

What does "next" mean?

It means:

Make the smallest possible change that results in a bigger permutation.

So we ask ourselves:

Step 1: Finding the Pivot (the dip point)

We scan from right to left and find the first place where the order breaks the descending pattern.

Why descending?

Because if the entire array is in descending order (like [5,4,3,2,1]), it is already the largest permutation.

Example:

1 *2* 5 4 3
   ↑
  2 > 4 fails

So the pivot is 2’s index.

This pivot is the point where we can make a “small increase”.

Step 2: Find the next greater element on the right

To make the permutation just slightly larger, we swap the pivot with the next greater element from its right side.

For our example, our next element greater than 2 from the right is 3, so we swap it with 2

1 3 5 4 2

Step 3: Reverse the remaining right portion

Once we swap, the right portion is still in descending order.

Reversing it gives the smallest lexicographical tail i.e. our result will be

1 3 2 4 5

This step finalizes the next permutation.

Why This Algorithm Works

Because lexicographical ordering is all about:

Making the smallest possible increase at the earliest position
Keeping the rest of the sequence as small as possible

This ensures we get the next permutation — not just any greater permutation.

Code Implementation (Java)

class Solution {
    public void nextPermutation(int[] nums) {
        int pivot = -1;
        int n = nums.length;

        // Step 1: Find pivot index
        for (int i = n - 1; i > 0; --i) {
            if (nums[i] > nums[i - 1]) {
                pivot = i - 1;
                break;
            }
        }

        // If no pivot found, array is in descending order
        if (pivot == -1) {
            Arrays.sort(nums); 
            return;
        }

        // Step 2: Find next greater element on the right of pivot
        for (int i = n - 1; i > pivot; --i) {
            if (nums[i] > nums[pivot]) {
                int temp = nums[i];
                nums[i] = nums[pivot];
                nums[pivot] = temp;
                break;
            }
        }

        // Step 3: Reverse the descending suffix
        reverse(nums, pivot + 1, n - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;

            left++;
            right--;
        }
    }
}

Conclusion

In conclusion, the problem looks intimidating at first because it deals with lexicographical order — something we usually do not think about explicitly.

But once you understand the three simple steps:

Find the pivot
Swap with the next greater element
Reverse the tail

…the problem becomes extremely intuitive.

This problem tests:

Pattern recognition
Understanding of permutations
Logical reasoning
Ability to write clean in-place algorithms

Master this once and it will stick with you forever.

Happy coding, friends!

Trapping Rain Water

we_are_broken_compilers — Sat, 29 Nov 2025 16:37:08 +0000

Hey fellow developers, welcome back to our DSA learning series. We hope
you are doing great and enjoying this journey with us. This series is
all about exploring problems the way a beginner genuinely sees them. We
are students ourselves, so we know exactly how confusing a problem can
look at first glance, and how a simple explanation at the right moment
can completely change the way you understand it. Today, we are going to
look at a very popular and very interesting problem --- Trapping Rain
Water.

This is a problem that almost every interviewer loves to ask. It is
marked as "Hard" on most platforms, but in reality, once you truly
understand what the question is trying to communicate, the whole logic
feels surprisingly intuitive. So let us take our time and walk through
the thought process slowly, step by step.

Problem Statement

We are given an array of non-negative integers that represent the
heights of vertical bars placed next to each other. Each bar has a width
of 1 unit. Now imagine rainwater falling on top of these bars. Depending
on the relative heights of the bars on the left and right, some amount
of water might get trapped between them. Our task is to determine how
much water gets accumulated in total.

For example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Brute Force Intuition

Let us start with the most straightforward idea --- the one that comes
to mind when you simply think about the situation as a person, not as a
coder.

Imagine you are standing at a particular bar of height h. To figure
out how much water can stay on top of this bar, you do not look only at
the bar itself; you quickly glance to your left and right. Water can
only stay if there is a taller boundary on both sides. So you check:

What is the tallest bar on my left?
What is the tallest bar on my right?

Then, the maximum water level above the current bar is determined by the
shorter of these two heights. Because water will spill over the smallest
boundary.

So the water trapped on index i becomes:

min(max height on left, max height on right) − current height

This idea is clean and logical. Now, to convert this into code, the
simplest approach is to run two loops for each index --- one scanning
leftward, and another scanning rightward. That gives us a clear
brute-force solution.

public int trap(int[] height) {
    int n = height.length;
    int totalWater = 0;

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

        // Find max on the left
        for (int j = i; j >= 0; j--) {
            maxLeft = Math.max(maxLeft, height[j]);
        }

        // Find max on the right
        for (int j = i; j < n; j++) {
            maxRight = Math.max(maxRight, height[j]);
        }

        int waterLevel = Math.min(maxLeft, maxRight) - height[i];
        totalWater += waterLevel;
    }

    return totalWater;
}

This solution works perfectly, and it is a good starting point because it forces us to understand the meaning behind the formula. However, it takes O(n²) time since for every index we scan the array twice. The space usage is constant, but the speed becomes an issue as input size grows.

Optimized Approach Using Prefix Arrays

Now that we understand the brute-force idea, let us refine it. Notice
that in the brute force solution, we repeatedly calculate the same
values --- the left maximum and right maximum for many positions. Why
not compute them once and reuse?

This leads to the prefix-max and suffix-max approach.

We create an array left[] where left[i] stores the maximum height
from index 0 to i.

Similarly, we create a right[] array where right[i] stores the
maximum height from index i to the last index.

Once these two arrays are ready, we already have all the information needed to compute the trapped water at every index in O(1) time. The final loop just applies the same formula as before.

Here is the code:

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if(n == 0) return 0;

        int[] left = new int[n];
        int[] right = new int[n];

        // Build prefix max array
        left[0] = height[0];
        for(int i = 1; i < n; ++i) {
            left[i] = Math.max(left[i - 1], height[i]);
        }

        // Build suffix max array
        right[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; --i) {
            right[i] = Math.max(right[i + 1], height[i]);
        }

        int trapped = 0;
        for(int i = 0; i < n; ++i) {
            trapped += Math.min(left[i], right[i]) - height[i];
        }

        return trapped;
    }
}

The time complexity now becomes O(n) and the logic becomes cleaner. The only trade-off is that we use two extra arrays, giving us O(n) space.

Final and Most Optimized Approach: Two-Pointer Technique

Finally, once we understand how prefix and suffix maxima help us, we can
push the optimization even further. The question becomes: Do we really need two whole arrays? The surprising answer is — no. We can keep track of everything we need using just two pointers (one starting from the left end and one from the right) and two variables (leftMax and rightMax) that update as we move inward. Here is the key observation: Water trapping at any point is limited by the smaller boundary between left and right. So, if height[left] is smaller, we focus on the left side. If height[right] is smaller, we shift our attention to the right side. This allows us to calculate trapped water on the fly while moving the pointers.

Here is the final optimized code:

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int trapped = 0;

        while (left < right) {

            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    trapped += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    trapped += rightMax - height[right];
                }
                right--;
            }
        }
        return trapped;
    }
}

This version gives us both O(n) time and O(1) space — the optimal combination.

Conclusion

By the time you reach this point, you have seen how the thought process evolves naturally: starting from a basic observation, moving to a brute-force method, then improving it with precomputed arrays, and finally refining it into the elegant two-pointer solution. And this journey is extremely important, because in interviews, most companies are not just looking for the final optimized answer — they want to hear how you build your logic step by step.

This problem is a great example of how understanding the idea is more valuable than memorizing the code. Once the concept becomes clear, all three approaches become easy to derive on your own.

Understanding the Logic Behind Two Sum — and Extending It to Three Sum

we_are_broken_compilers — Sat, 08 Nov 2025 18:10:50 +0000

Welcome back to our DSA Learning Series — where we pick one problem at a time, understand its logic deeply, and write clean, beginner-friendly code.

The Three Sum problem is a favorite among interviewers because it tests layered logical thinking — combining array traversal, the two-pointer technique, and duplicate handling.

But before tackling Three Sum, it’s crucial to fully understand the Two Sum logic, especially when the array is sorted.

Revisiting Two Sum (in a Sorted Array)
Problem Statement
Given a sorted array and a target sum, find two numbers whose sum equals the target.

Example:

Input: nums = [-3, -1, 0, 2, 4, 5], target = 3

Output: [1, 2] -- since nums[1] + nums[2] = 3

Intuition
If the array is sorted, we can use the two-pointer approach instead of nested loops for efficiency.

Steps:

Place one pointer at the start (left) and another at the end (right).
Calculate the sum of both numbers.
If sum == target, we found the pair.
If sum < target, move the left pointer forward (to increase the sum).
If sum > target, move the right pointer backward (to decrease the sum).

This way, we traverse the array only once — giving an O(n) solution.

Code: Two Sum (Sorted Array)

int left = 0;
int right = nums.length - 1;

while (left < right) {
    int sum = nums[left] + nums[right];

    if (sum == target) {
        System.out.println("Pair found: " + nums[left] + ", " + nums[right]);
        left++;
        right--;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

Extending the Logic to Three Sum
Once the Two Sum logic is clear, we can easily extend it to handle three numbers. Let's take a look at the below problem to understand the logic deeper.

Problem Statement
Find all unique triplets in the array whose sum equals 0.

Example:

Input: nums = [-1, 0, 1, 2, -1, -4]

Output: [[-1, -1, 2], [-1, 0, 1]]

Step-by-Step Intuition

Sort the array.
Sorting helps handle duplicates and makes the two-pointer logic work properly.
Fix one element (nums[i]).
Then apply the Two Sum approach on the remaining part of the array.
Set a new target:
Since we want nums[i] + nums[left] + nums[right] = 0,
the new target becomes -nums[i].
Move pointers (left, right) based on the current sum.
If sum == 0, store the triplet.
Skip duplicates to avoid repeated triplets.
Adjust pointers (left++, right--) accordingly.

Code: Three Sum (Two-Pointer Approach)

Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();

for (int i = 0; i < nums.length - 2; i++) {
    // Skip duplicate elements for the first number
    if (i > 0 && nums[i] == nums[i - 1]) continue;

    int left = i + 1;
    int right = nums.length - 1;

    while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];

        if (sum == 0) {
            result.add(Arrays.asList(nums[i], nums[left], nums[right]));

            // Skip duplicates for left and right
            while (left < right && nums[left] == nums[left + 1]) left++;
            while (left < right && nums[right] == nums[right - 1]) right--;

            left++;
            right--;
        } else if (sum < 0) {
            left++;
        } else {
            right--;
        }
    }
}

Why This Works

The outer loop fixes one element (nums[i]).

The inner loop uses the Two Sum logic to find pairs that sum to negative of nums[i].

Sorting enables:

Skipping duplicates easily.
Using the two-pointer pattern effectively.

This approach efficiently finds all unique triplets in O(n²) time — which is optimal for this problem.

What was your aha moment while reading this?
Let us know — and don’t forget to share this post with someone preparing for their coding interviews!

Merge K Sorted Lists

we_are_broken_compilers — Thu, 30 Oct 2025 12:21:29 +0000

Before we dive in, note that in our previous article we walked through how to merge two sorted linked lists, step by step. That idea is the core building block for what we will do here.

If you would like a quick refresher first, check out the guide: 🔗 Merge Two Sorted Linked Lists

Once you’re comfortable with that, come back here — we’ll take it one level higher and learn how to merge K sorted lists efficiently.

In this post we will break the problem down, explain the intuition, and walk through a clear example so the idea sticks

Problem Statement

You are given K linked lists — each sorted in ascending order.
Your task is to merge them all into one single sorted linked list.

Sample Input: lists = [[1,4,5],[1,3,4],[2,6]]
Sample output: [1,1,2,3,4,4,5,6]

The Intuition — Think of It Like Paper Sheets
Imagine you have 4 already sorted papers of numbers.

If you merge all 4 one by one, like this:
Merge 1 + 2 → result1
Then result1 + 3 → result2
Then result2 + 4 → result3

That works… but it’s slow because you keep merging bigger and bigger lists repeatedly.

A smarter way?

Merge them in pairs!

Round 1: Merge (List0 + List1), (List2 + List3)

Round 2: Merge the two merged results

Done !!!

This is exactly what our code does — merge lists in pairs, doubling the group size each time.

The Code

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        int interval = 1;
        int n = lists.length;

        while (interval < n) {
            for (int i = 0; i + interval < n; i = i + interval * 2) {
                lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }

        return lists[0];
    }
}

Step-by-Step Explanation

Step 1 — Base check

if (lists == null || lists.length == 0) return null;

If no lists exist, just return null.

Step 2 — Start with interval = 1

We’ll first merge lists that are next to each other:

interval = 1 → merge (0,1), (2,3), (4,5)...

Step 3 — Merge pairs inside a loop

for (int i = 0; i + interval < n; i = i + interval * 2)

That scary line simply means:

Go through the lists array, merge list[i] with list[i + interval],
then skip ahead by interval * 2 to jump to the next pair.

So for:

interval = 1: merge (0,1), (2,3)

interval = 2: merge (0,2), (4,6)

Step 4 — Replace the merged list

lists[i] = mergeTwoLists(lists[i], lists[i + interval]);

After merging two sorted lists, store the result in lists[i].

Step 5 — Double the interval
interval *= 2;

After each round, we’ve merged lists into bigger groups, so next time we double the interval.

Why interval doubles and i = i + interval 2*

Why interval doubles and i = i + interval * 2

Round	Interval	Pairs Merged	What Happens
1	1	(0,1), (2,3)	Merge small lists
2	2	(0,2)	Merge bigger merged lists
3	4	—	Done (only one list left)

Each merge round combines 2×bigger lists,
so we double the interval and jump ahead by interval * 2.

Time Complexity

Let’s break it down:

Each merge operation takes O(N) (where N is total elements).

Each round halves the number of lists.

So total complexity = O(N log K).

✅ Much faster than merging one by one (which is O(NK)).

Final Thoughts

The key to understanding Merge K Sorted Lists is realizing that:

You don’t merge them one-by-one — you merge them in pairs, in rounds.

This divide-and-conquer pattern is clean, efficient, and elegant — it’s the same concept that powers merge sort!

Merge Two Sorted Linked Lists

we_are_broken_compilers — Sun, 26 Oct 2025 09:40:16 +0000

Welcome back to our DSA Learning Series — where we pick one problem at a time, understand its logic deeply, and write clean, beginner-friendly Java code.

The problem that we are going to discuss today is a classic in linked lists — Merge Two Sorted Lists

It is a foundational question that not only strengthens your understanding of linked list traversal but also acts as the building block for more advanced problems like Merge K Sorted Lists, which we will explore in the next article.

Problem Statement

We are given two sorted linked lists. Our task is to merge them into a single sorted linked list.

Example:

Input:
List1: 1 → 3 → 5
List2: 2 → 4 → 6

Output:
1 → 2 → 3 → 4 → 5 → 6

Intuition

The idea is simple — both lists are already sorted. So we can use two pointers to traverse them by always picking the smaller value first and then continue until one list finishes, and then ultimately attach the remaining part of the other list.

🧱 Step 1: Iterative Approach
In this approach, we use a dummy node to simplify pointer handling. This dummy node helps us build the final list step by step without worrying about the head pointer separately.

Code

/**
 * 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) {
        ListNode dummy = new ListNode(); // this is the dummy node to start the merged list
        ListNode pointer = dummy; // this pointer is used to build the new list

        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                pointer.next = list1; // attach the smaller node
                list1 = list1.next;   // move list 1 pointer ahead
            } else {
                pointer.next = list2;
                list2 = list2.next; // move list 2 pointer ahead
            }

            pointer = pointer.next; // move result pointer ahead
        }

        // attach the remaining nodes
        if(list1 == null) {
            pointer.next = list2;
        } else {
            pointer.next = list1;
        }

        return dummy.next; // finally return the merged list formed at dummy's next
    }
}

Step-by-Step Example
Let’s merge the below two lists:
List1 = 1 → 3 → 5
List2 = 2 → 4 → 6

Step	list1	list2	Chosen Node	Merged List So Far
1	1	2	1	1
2	3	2	2	1 → 2
3	3	4	3	1 → 2 → 3
4	5	4	4	1 → 2 → 3 → 4
5	5	6	5	1 → 2 → 3 → 4 → 5
6	null	6	6	1 → 2 → 3 → 4 → 5 → 6

🌀 Step 2: Recursive Approach

Code

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if(l1 == null) return l2;
    if(l2 == null) return l1;

    if(l1.val <= l2.val) {
        l1.next = mergeTwoLists(l2, l1.next);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

How the above approach works:

The smaller node between l1 and l2 becomes part of the merged list.
The function then recursively merges the rest of the nodes.
The recursion continues until one list is empty.

This version is clean and expressive, though it uses extra call stack space (O(n + m) in the worst case).

Complexity Analysis

As each node is processed exactly once, the time complexity will be O(n + m), where n and m are the sizes of corresponding lists.

Regarding the space complexity, it is constant for iterative solution - O(1). However recursive solution adds the stack space resulting in O(n + m)

Final thoughts

This problem teaches one of the most important linked list patterns — merging while maintaining order.

It forms the foundation for more advanced problems like Merge K Sorted Lists, which we will discuss in the next article by following a Divide and Conquer approach.

💬 Your Turn:
Try implementing both iterative and recursive versions yourself. and let us know which one feels more intuitive to you — pointer manipulation or recursion?

Stay tuned and keep practicing!

Next Greater Element (Right) using Stack

we_are_broken_compilers — Thu, 23 Oct 2025 11:04:50 +0000

Welcome back to Day 3 of our DSA Problem Series, where we explore one problem each day, understand its logic, and break it down into clean Java code.

Today’s challenge is a classic stack-based problem —
👉 Find the Next Greater Element on the Right (NGE) for every element in the array.

Problem Statement

Given an array of integers, for every element, find the next greater element that appears to its right.
If there’s no greater element, store -1 for that position.

Example:
Input: [ 4, 5, 2, 10, 8 ]
Output: [ 5, 10, 10, -1, -1 ]

Explanation:

For 4, next greater is 5
For 5, next greater is 10
For 2, next greater is 10
For 10, no greater element → -1
For 8, no greater element → -1

Brute Force Thought

A straightforward approach would be:

For each element, look to its right until you find a greater number.
But that gives O(n²) time complexity — not ideal for large arrays 😓

We can do better with a stack.

Optimized Stack-Based Solution (O(n))

public static int[] nextGreator(int[] arr) {
    Stack<Integer> st = new Stack<>();
    int[] result = new int[arr.length];

    for (int i = arr.length - 1; i >= 0; i--) {
        // Pop smaller or equal elements from stack
        while (!st.isEmpty() && arr[i] >= arr[st.peek()]) {
            st.pop();
        }

        // If stack is empty, no greater element to the right
        result[i] = st.isEmpty() ? -1 : arr[st.peek()];

        // Push current index onto the stack
        st.push(i);
    }
    return result;
}

How this approach works...

Idea:

Use a stack to keep track of elements for which we have not yet found the next greater element. Traverse the array from right to left so that the elements to the right are already processed.
Step-by-Step:
- Initialize an empty stack and a result array.
- For each element (starting from the end of the array):
  1. Pop smaller elements from the stack, because they cannot be the next greater for the current element.
  2. If the stack is empty after popping, there is no greater element to the right — store -1.
  3. If the stack is not empty, the element at the top of the stack is the next greater element — store it in the result.
  4. Push the current element (or its index) onto the stack for future comparisons.
Why it works:
- The stack always contains elements that are potential candidates for next greater elements of elements to their left.
- Each element is pushed and popped at most once, giving an efficient O(n) solution.

Step-by-Step Dry Run

Let’s dry-run it for arr = [4, 5, 2, 10, 8].

i	arr[i]	Stack (indices)	Next Greater	Result[]
4	8	[]	-1	[-,-,-,-,-1]
3	10	[4]	-1	[-,-,-,-1,-1]
2	2	[3]	10	[-,-,10,-1,-1]
1	5	[3]	10	[-,10,10,-1,-1]
0	4	[1,3]	5	[5,10,10,-1,-1]

Output: [5, 10, 10, -1, -1]

Time and Space Complexity comparison

Operation	Description	Complexity
Traversal of array	Each element is visited once (from right to left)	O(n)
Stack operations (push/pop)	Each element is pushed and popped at most once	O(n)
Total Time Complexity	Traversal + Stack operations	O(n)
Space Complexity	Stack + Result array	O(n)

Final Thoughts

This problem forms the base for many variations like:

Next Greater Element (Left)
Next Smaller Element (Right/Left)
Stock Span Problem
Largest Rectangle in Histogram

So make sure you truly understand this one — it’ll come in handy often!

Your Turn!

Try modifying the code for:

🔁 Next Smaller Element (Right)

Can you spot the small change needed? 😉

Bonus Challenge:
Also, try writing the brute force solution and analyze its time complexity.
Can you explain why the stack-based approach is faster?

💬 Share your version or your reasoning in the comments below — We'd love to see how you approach it!

Delete N Nodes After M Nodes of a Linked List

we_are_broken_compilers — Wed, 22 Oct 2025 17:32:17 +0000

Hey everyone!
This is our second article in the DSA learning series where we aim to grow together — one problem at a time.

Our goal remains the same: to make concepts simpler, logic clearer, and learning collaborative.

Problem Statement

In this problem we are given a linked list, and we have to perform the following operations:
Keep M nodes, then delete N nodes, and keep repeating this until the end of the list.

Example:
Input:
Linked List: 9 → 1 → 3 → 5 → 9 → 4 → 10 → 1

M = 2, N = 1

Output:
9 → 1 → 5 → 9 → 10 → 1

Explanation:
Skip 2 nodes (9, 1), delete the next 1 (3), then skip 2 again (5, 9), delete next (4), and continue.

Thought Process

This is one of those pointer problems where clarity beats complexity.

We can solve this cleanly using just one loop — by breaking the task into repeatable chunks:

Skip M nodes — these are the nodes we keep.
Delete N nodes — we move a second pointer ahead by N, cutting them out of the chain.
Connect the last kept node to the node after the deleted segment.
Repeat until the list ends.

This approach is iterative, clean, and runs in O(length of list).

Code Implementation

static void linkdelete(Node   head, int m, int n) {
    Node temp = head;

    while (temp != null) {
        // Skip M nodes (we are already on the 1st one)
        int countM = 1;
        while (countM < m && temp != null) {
            temp = temp.next;
            countM++;
        }

        // If we reached the end, nothing to delete
        if (temp == null) return;

        // Start deleting next N nodes
        Node sampleTemp = temp.next;
        int countN = 1;
        while (countN <= n && sampleTemp != null) {
            sampleTemp = sampleTemp.next;
            countN++;
        }

        // Connect Mth node to the node after deleted segment
        temp.next = sampleTemp;

        // Move temp to the next segment
        temp = sampleTemp;
    }
}

⚙️ Time and Space Complexity

Type	Complexity	Explanation
Time	O(L)	We traverse each node once
Space	O(1)	Only pointers and counters used

Wrapping Up

This problem is a great exercise in pointer control and in-place modification.
We hope our explanation helped you connect the logic step by step and see how iterative thinking simplifies complex pointer tasks.

💬 We’d love your support!
Share your feedback, ask questions, and let’s keep learning together — one DSA problem at a time.

DSA Series by Broken Compilers.
Follow our journey as we learn, teach, and grow through code.

Forem: we_are_broken_compilers

Largest Subarray with 0 sum

Problem Statement

Explanation:

First Approach (Brute Force)

Code (Java – Brute Force)

Problem with this approach

Optimized Approach (Prefix Sum + HashMap)

Optimized Code (Java – O(n))

Complexity Analysis

Koko Eating Banana

First Thought on Reading the Problem

Key Observation

Solution Approach

Feasibility Check Logic

Code (Java)

Time Complexity

Time Complexity: O(n log maxPile)

Binary Search

Feasibility Check (isPossible)

Total

Space Complexity

Space Complexity: O(1)

Final Words

Minimum Time to Complete Trips

Hey fellow developers 👋

Problem Statement

Understanding the Idea

Brute Force Approach

Idea

Brute Force Code (Java)

Why trips += T / t Works

Complexity (Brute Force)

Optimal Approach (Binary Search on Answer)

Key Observation

Search Space

Binary Search Logic

Optimal Code (Java)

Complexity (Optimal)

Final Thoughts

Minimum Rounds to Complete All Tasks

Explanation

Approach (Greedy + HashMap)

Code (Java)

Complexity Analysis

Delete a Node in a Binary Search Tree (BST)

Quick Reminder: What Makes a BST Special?

Problem Statement

Finding the Node First

The Three Deletion Cases

Case 1: Node Has No Children (Leaf Node)

Case 2: Node Has One Child

Case 3: Node Has Two Children (The Interesting One)

Putting It All Together — Code

Final Thoughts

Next Permutation — Intuition, Explanation, and Clean Implementation

Problem Statement

Understanding the Core Idea

Step 1: Finding the Pivot (the dip point)

Step 2: Find the next greater element on the right

Step 3: Reverse the remaining right portion

Why This Algorithm Works

Code Implementation (Java)

Conclusion

Trapping Rain Water

Problem Statement

Brute Force Intuition

Optimized Approach Using Prefix Arrays

Final and Most Optimized Approach: Two-Pointer Technique

Conclusion

Understanding the Logic Behind Two Sum — and Extending It to Three Sum

Merge K Sorted Lists

Problem Statement

The Code

Step-by-Step Explanation

Why interval doubles and i = i + interval * 2

Time Complexity

Merge Two Sorted Linked Lists

Problem Statement

Intuition

Time Complexity: `O(n log maxPile)`

Feasibility Check (`isPossible`)

Space Complexity: `O(1)`

Why `trips += T / t` Works

Why interval doubles and i = i + interval 2*