Summary of "3 Sum | Brute - Better - Optimal with Codes"

Summary of “3 Sum | Brute - Better - Optimal with Codes”

This video is a detailed tutorial on solving the classic 3 Sum problem from Data Structures and Algorithms (DSA). It is part of Striver’s A to Z DSA course, an in-depth resource for mastering DSA with over 455 modules and 400+ problems solved.

Problem Statement

Given an array of integers, find all unique triplets (three elements) whose sum is zero.
Important constraints:
- Each element in a triplet must be distinct by index (i ≠ j ≠ k).
- No duplicate triplets should be returned (triplets with the same elements in any order count as duplicates).

Approaches Covered

1. Brute Force Solution (O(n³))

Concept:

Use three nested loops to try all possible triplets.
Check if the sum of the three elements is zero.
To avoid duplicates, sort each triplet before storing.
Use a set data structure to store sorted triplets uniquely.

Steps:

Loop i from 0 to n-3.
Loop j from i+1 to n-2.
Loop k from j+1 to n-1.
If arr[i] + arr[j] + arr[k] == 0, sort the triplet and insert into a set.

Complexity:

Time: O(n³) due to three nested loops.
Space: O(m), where m is the number of unique triplets (due to the set and answer list).

Drawback: Time limit exceeded for large inputs; inefficient.

2. Better Solution Using Hashing (O(n² log m))

Concept:

Reduce one loop by fixing two elements and searching for the third element using hashing.
For fixed i and j, the third element needed is -(arr[i] + arr[j]).
Use a hash set to check if this third element exists among previously seen elements.

Key Points:

Reset hash set for every new i.
Insert elements into the hash set as you iterate over j.
To avoid duplicates, sort the triplet before adding it to the answer set.

Steps:

Loop i from 0 to n-2.
Initialize empty hash set.
Loop j from i+1 to n-1.
Calculate third = -(arr[i] + arr[j]).
If third in hash set, add sorted triplet to answer set.
Add arr[j] to hash set.

Complexity:

Time: Approximately O(n² log m) due to two loops and set insertion/search.
Space: O(n + m) for hash set and answer set.

Drawback: Still uses extra space for sets; interviewer might ask for further optimization.

3. Optimal Solution Using Sorting + Two Pointers (O(n²))

Concept:

Sort the array first.
Fix one element i, then use two pointers j (start) and k (end) to find pairs summing to -arr[i].
Move pointers based on sum comparison:
- If sum < 0, move j forward to increase sum.
- If sum > 0, move k backward to decrease sum.
- If sum == 0, record triplet and move both pointers, skipping duplicates.

Key Points:

Avoid duplicates by skipping equal elements for i, j, and k.
Since array is sorted, no need for extra data structures to filter duplicates.

Steps:

Sort array.
For i in 0 to n-3:
- Skip if arr[i] is same as previous to avoid duplicates.
- Set j = i+1, k = n-1.
- While j < k:
  - Calculate sum = arr[i] + arr[j] + arr[k].
  - If sum == 0, add triplet and move pointers skipping duplicates.
  - Else if sum < 0, move j forward.
  - Else move k backward.

Complexity:

Time: O(n log n) for sorting + O(n²) for two-pointer traversal → O(n²).
Space: O(m) for answer list (m = number of unique triplets), O(1) auxiliary space.

Advantages:

Efficient and accepted in interviews.
No extra data structures for duplicate handling.
Clean and elegant approach.

Additional Notes

Sorting the triplets or the array is critical to avoid duplicates.
Using sets helps in brute and better solutions but adds extra space.
Two-pointer approach leverages sorted array properties to optimize search and duplicate avoidance.
The video includes detailed code walkthroughs for all three approaches.
Time and space complexities are analyzed and explained for each method.
Viewers are encouraged to try the problem themselves from the provided link.

Speakers / Source

The entire explanation and code walkthrough are provided by Striver, the creator of the Striver’s A to Z DSA course.
No other speakers are featured.

Summary

The video teaches how to solve the 3 Sum problem with three approaches:

Brute Force: Triple nested loops with a set to remove duplicates (O(n³)).
Better: Two loops plus hashing to find the third element (O(n² log m)).
Optimal: Sort array + two-pointer technique to find pairs summing to target, skipping duplicates without extra space (O(n²)).

This progression shows how to optimize a naive solution into an interview-ready efficient algorithm.