DEV Community: Ashu Sharma

3Sum Closest

Ashu Sharma — Sat, 21 Jun 2025 05:11:41 +0000

So I Heard You Like ...Sums? My Take on 3Sum Closes

Alright, it's becoming a habit to share my first reaction to these problems, so here we go. When I saw "3Sum Closest," my brain pretty much went:

I mean, I'd already conquered 2Sum, 3Sum, and even battled through 4Sum. Don't get me wrong, I love a good trilogy (and its questionable fourth installment), but this felt like a sequel I didn't ask for.

But this one is a little different. It’s got a fun twist! We don't need to find a triplet that equals a target. Instead, we need to find the one whose sum is the closest.

There could be many triplets, and we need to figure out which one is the "closest." So, what does "closer" even mean here? Well, think of it like a number line. You just subtract the triplet's sum from the target and take the absolute value. The smaller that result, the cozier you are to the target. That's our mission.

The game plan is actually pretty similar to the original 3Sum. Ohh! and we need to sort our vector/array before we do anything. Now you start with a for loop that runs through each element, let's call its iterator i.

From there, we get to use the classic two-pointer strategy. We'll plant a left pointer at i + 1 and a right pointer at the very end of the array. Now we have our triplet!

With our three numbers, we calculate the sum. Then, as I mentioned, we find the current_difference between this sum and our target. This is where we need to keep score. We'll have a couple of variables, min_difference and closest_sum, to remember the best we've seen so far.

Every time we calculate a new sum, we check: is this new guy even closer than our current champion?

if (abs(target - sum) < min_difference) {
    min_difference = abs(target - sum);
    closest_sum = sum;
}

Simple enough, right? Now we just need to move our pointers in that slick, efficient way we all learned from the 2Sum problem.

if (sum < target) {
    left++;
} else if (sum > target) {
    right--;
} else {
    return sum;
}

Now, you might be looking at that else block and thinking, "Hold on, why are you returning the sum right away?"

Think about it for a second. If our sum actually equals the target, can we possibly get any closer? Nope! That's a bullseye. It's the undisputed, all-time champion of "closest." So, we can just return it and call it a day.

But if we get through the whole loop and never hit that perfect match, no sweat! Our closest_sum variable has been faithfully remembering the next best thing the whole time. We just return that at the very end.

And that's it! That's the 3Sum Closest problem for you.

Happy Coding!

Dutch National Flag Problem

Ashu Sharma — Sat, 14 Jun 2025 03:22:44 +0000

So this time I was given the below problem:

Given an array 'nums' with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

My brain immediately went:

I had a gut feeling this was about rearranging and grouping elements. My intuition screamed "pointers!" Not just two, but three. Also I get to know that this classic problem is often called the Dutch National Flag problem.

The Game Plan: Three Pointers for Three Colors
The goal is to partition the array into three sections: all the 0s at the beginning, all the 1s in the middle, and all the 2s at the end.

To do this in a single pass, we'll use three pointers:

left: This pointer marks the boundary for our "red" (0) section. Everything to the left of left is a confirmed 0.
middle: This is our main iterator. It scans the array, and its job is to figure out where the element nums[middle] belongs.
right: This pointer marks the boundary for our "blue" (2) section. Everything to the right of right is a confirmed 2.

Our loop will run as long as middle <= right, shrinking the "unknown" section between middle and right until it disappears.

The Logic in Action
We iterate through the array with our middle pointer and handle three simple cases:

Case 1: nums[middle] is a 0 (Red) 🔴
If nums[middle] is a 0, it belongs in the left section. So, we swap the element at middle with the element at left.

swap(nums[left], nums[middle]);

Since we now have a confirmed 0 at the left position, we can advance our left pointer. We also advance the middle pointer because the element we just swapped into the middle position has already been processed (we'll dive into why in a moment).

left++;
middle++;

Case 2: nums[middle] is a 1 (White) ⚪
If nums[middle] is a 1, it's already in the right potential spot! The middle section is where 1s are supposed to live. We don't need to swap anything. We just move on to the next element.

middle++;

Case 3: nums[middle] is a 2 (Blue) 🔵
If nums[middle] is a 2, it belongs at the end of the array, in the right section. So, we swap it with the element at the right pointer.

swap(nums[middle], nums[right]);

After the swap, we know the element now at right is a 2, so we can shrink our right boundary inward.

right--;

But notice we don't advance middle here! Why? The element we just received from the right position is a complete unknown. It could be a 0, 1, or even another 2. We need to re-evaluate the new element at nums[middle] in the next loop iteration.

The "Aha!" Moment: Why Pointer Moves Differ

This was the key insight for me:

When we swap nums[middle] == 0 with nums[left], we know the element coming to middle was already in the processed zone (left of middle). Because of our algorithm's structure, any element between left and middle can only be a 1. So, after the swap, nums[middle] is guaranteed to be a 1 (or a 0 if left and middle started at the same spot). In either case, the element at middle is handled, and we can confidently move middle forward.

When we swap nums[middle] == 2 with nums[right], the element coming to middle is from the unprocessed, unknown part of the array. We must re-check it to see if it's a 0, 1, or 2 before moving middle.

This simple but powerful logic allows us to sort the array in one pass with constant extra space.

Index Negation Technique

Ashu Sharma — Sat, 07 Jun 2025 03:04:06 +0000

So I was asked a question find the missing number(s) in an array where the elements are in the range of [1,n] and it(array) contains n integers

Input: [4,3,2,7,8,2,3,1] (n=8, range=[1,8]) 
Output: {5,6}

My first Reaction

My first instinct was to go with a straightforward brute-force solution. But reality hit hard. If I go Brute Force, I will have to pick each number from 1 to n and then search for that number in my input array. That means if my array is too large, it's going to take a lot of operations (O(n^2) time complexity, to be exact). Nobody likes that.

So, I discovered this clever approach called the Index Negation Technique.

THE INDEX NEGATION TECHNIQUE

But before I explain this technique, I want to remind all of you of a very basic concept related to the problem's constraints:

For an array where elements are in the range [1, n], if it were sorted, every element x would be placed at index x-1. For example, the number 1 would be at index 0, the number 2 at index 1, and so on.

This mapping between a value and an index is the foundation of our trick.

Now, here's how the technique works:

You pick an element from the input array. Let's call this value num. You then find the index where num would have been placed if the array was sorted (which is index = abs(num) - 1).

Once that index is found, you negate the value at that specific index to mark it as "seen". You do this for every element in the array.

By doing this, you are using the array itself to keep track of which numbers have been found.

So, why do we need abs()?

That's a great question, and it's the key to making this technique robust. The algorithm would break without using the absolute value (abs()) for two main reasons. Let's use our example: [4,3,2,7,8,2,3,1].

To handle values at indices that have already been negated.

Imagine our loop is processing the array. We start with the 4, then the 3. When we process the 3 (at index 1), we go to index 2 and negate the value there.

Initial array: [4, 3, 2, 7, ...]
After processing 3: [4, 3, -2, 7, ...]

A moment later, our loop arrives at index 2 to process the element there. The value it reads is no longer 2, but -2.

Without abs(): We would try to calculate the target index for -2, which would be -2 - 1 = -3. This is an invalid index and would crash the program.
With abs(): We take abs(-2), which gives us 2. We then calculate the target index as 2 - 1 = 1. This correctly tells us that the number 2 corresponds to index 1, allowing the algorithm to proceed correctly.

To correctly process duplicate numbers.

Our example has two 2s and two 3s. Let's see what happens with the two 2s.

When the algorithm first encounters a 2, it goes to index 1 (since 2-1=1) and negates the value there.

Later, when the algorithm encounters the second 2, it needs to do the same thing. It takes abs(2), finds index 1, and sees the value there is already negative. This confirms that a 2 has already been seen, so it simply moves on.

In short, abs() ensures we always use a number's magnitude to find its correct home index. It makes the algorithm work regardless of the order of the elements or whether the values we are reading have already been flipped to negative by a previous step.

Finding the Final Answer

Once you have iterated through the entire input array, you make one final pass. You can just see which values in the array are still positive. A positive value at index i implies that the number i+1 was never present in the original input. These are your missing values!