3 and 4 Sum optimized Approach

StriKing_sHadOws — Mon, 18 May 2026 17:25:01 +0000

3 Sum problem(2 pointer approach)
Here,I discussed classic problem of both 3 Sum and 4 Sum problem.
3 Sum Problem
Problem Statement

Find all unique triplets in an array whose sum equals 0.
ex-[-1, 0, 1, 2, -1, -4] o/p-[-1, -1, 2],
[-1, 0, 1]

Approach Using Two Pointers
Step 1 — Sort the Array

Sorting helps:

Use two pointers efficiently
Handle duplicates easily

Step 2 — Fix One Element

Choose one element at a time.

For example:

Fix -1

Now we need two more numbers whose sum becomes 1

Step 3 — Use Two Pointers

Place:

One pointer after the fixed element
One pointer at the end

Now:

If the sum is too small → move left pointer forward
If the sum is too large → move right pointer backward
If the required sum is found → store the triplet

This reduces the complexity from O(n³) to O(n²).

Important Observation

Since the array is sorted:

Moving left pointer increases the sum
Moving right pointer decreases the sum

This is the main reason why the two pointer technique works efficiently.

Handling Duplicates

Duplicate triplets should not appear in the final answer.

So while traversing:

Skip repeated fixed elements
Skip repeated pointer values after finding a valid triplet

This ensures only unique triplets are stored.

Time Complexity of 3 Sum
| Approach | Complexity |
| -------------------- | ---------- |
| Brute Force | O(n³) |
| Two Pointer Approach | O(n²) |

4 Sum
Problem Statement

Find all unique quadruplets whose sum equals a given target.

Example:nums = [1,0,-1,0,-2,2]
target = 0
o/p-[-2,-1,1,2]
[-2,0,0,2]
[-1,0,0,1]

Approach Using Two Pointers

The logic is very similar to the 3 Sum problem.

Step 1 — Sort the Array

Sorting again helps in:

Efficient traversal
Duplicate handling
Applying two pointers
Step 2 — Fix Two Elements

In 4 Sum:

First fix one element
Then fix a second element

Now we only need to find two remaining numbers.

This becomes similar to the 2 Sum problem.

Step 3 — Apply Two Pointers

Use:

Left pointer
Right pointer

Now:

Increase left pointer if sum is smaller
Decrease right pointer if sum is larger
Store answer if target is achieved
Why 4 Sum Becomes Efficient

Brute force checks every quadruplet:O(n⁴)

Using sorting + two pointers:O(n³)

Click it to see the codes of both

Key Takeaways

The 3 Sum and 4 Sum problems are powerful examples of:

How sorting simplifies problems
How two pointers reduce complexity
How observation can optimize brute force solutions

The two pointer technique is widely used in:

Pair sum problems
Sliding window problems
Array optimization questions
Interview-level DSA questions

Mastering this technique makes many advanced problems easier.

Conclusion

The biggest lesson from 3 Sum and 4 Sum is that:

A sorted array combined with smart pointer movement can eliminate unnecessary computations efficiently.

Instead of checking every possible combination:

We intelligently move pointers
Reduce time complexity
Avoid duplicates naturally

These problems are a must-learn for anyone preparing for coding interviews or competitive programming.

3 Sum Problem

StriKing_sHadOws — Mon, 18 May 2026 00:51:10 +0000

**Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

The way to solve this problem is given in following repository link below:

I have only discussed bruteforce and better approach**

click it to preview code

Thanks

DEV Community: StriKing_sHadOws

3 and 4 Sum optimized Approach

3 Sum Problem