Solving the 3Sum Problem in Dart: A Clean and Efficient Approach

Recently, I tackled one of the classic algorithm challenges—3Sum—and decided to implement the solution in Dart, a language often overlooked for such algorithmic problems. Here’s a deep dive into the thought process, optimizations, and final implementation.

The Problem: 3Sum

Given an array of integers nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that:

• i != j, i != k, and j != k

• nums[i] + nums[j] + nums[k] == 0

The catch? You must avoid duplicate triplets in your final result.

---

The Strategy

The naive approach—using three nested loops—would have a time complexity of O(n³), which isn’t practical for large inputs.

Instead, we:

1. Sort the array to manage duplicates easily.

2. Fix one number and use a two-pointer technique to find the other two numbers that complete the triplet.

This improves the time complexity to O(n²), which is much more acceptable.

---

The Dart Implementation

class Solution {
  List<List<int>> threeSum(List<int> nums) {
    List<List<int>> result = [];

    // Sort the array to handle duplicates and use two-pointer approach
    nums.sort();

    for (int i = 0; i < nums.length - 2; i++) {
      // Skip duplicate elements
      if (i == 0 || nums[i] != nums[i - 1]) {
        int l = i + 1, r = nums.length - 1;
        int sum = -nums[i];

        while (l < r) {
          if (nums[l] + nums[r] == sum) {
            result.add([nums[i], nums[l], nums[r]]);

            // Skip duplicates
            while (l < r && nums[l] == nums[l + 1]) l++;
            while (l < r && nums[r] == nums[r - 1]) r--;

            l++;
            r--;
          } else if (nums[l] + nums[r] < sum) {
            l++;
          } else {
            r--;
          }
        }
      }
    }

    return result;
  }
}

---

🔍 Key Highlights

• Sorting: Sorting makes duplicate detection easy and lets us use the two-pointer method efficiently.

• Duplicate Check: By skipping over repeated numbers (both at the start and inside the loop), we ensure no repeated triplets in the result.

• Two-Pointer Magic: Fix one element, and then slide two pointers (l and r) inward based on whether the sum is too small or too big.

---

🧪 Sample Input & Output

final solution = Solution();
print(solution.threeSum([-1, 0, 1, 2, -1, -4]));
// Output: [[-1, -1, 2], [-1, 0, 1]]

---

🧠 Final Thoughts

This solution strikes a great balance between clarity and efficiency. Using Dart for this kind of problem also shows its versatility beyond just Flutter development. If you’re prepping for interviews or building up your algorithmic chops, challenges like 3Sum are fantastic practice.