Leetcode - 3Sum

Question

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.

Idea

• Sort input array
  • Intuition here is that we want to shrink our search space by searching things to the right of i
• Iterate through input array
  • Establish l and r pointers move towards each other from opposite ends of our search space (to the right of i since we are a sorted array here)
  • If nums[i] > 0, check if our current num is the same as the last index, then skip if true to avoid duplicates
  • For each i, search for two others values that solve the problem
  • Our subproblem is effectively 2 sum for a given i, where target = 0 - nums[i] so we want nums[j] + nums[k] == target (which is our 2 sum problem)
  • Based on our current sum we can increment l or decrement r depending on if we are higher or lower than our target
  • If we find a match, add to res and then shrink our search window, where here we want to skip over duplicates as well so that we don’t look at the same index for our subproblem
• Sort of intuitive thought process to solve but those duplicates got me

Solution