Minimum Swaps to Group All 1's Together
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.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
.
The distinct triplets are [-1,0,1]
and [-1,-1,2]
.
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
Solution
Since we have learned how to find 2 Sum given a sorted array, 3 Sum is just one more number added onto the 2 sum. We can wrap the two pointer 2 sum implementation by a for loop that chooses the first element of the 3 sum for us. Using the deduplication patterns from Deduplication, we can easily find unique triplet that sums to 0.
- We avoid duplicate first element by checking whether
nums[i] == nums[i-1]
in every iteration. - We avoid duplicating the second element by checking whether
nums[l] == nums[l-1]
in the selection of the left pointer. - The value of the third element is based on the first and second elements, thus the triplets will be unique.
Implementation
1def threeSum(self, nums: List[int]) -> List[List[int]]:
2 nums.sort()
3 res = []
4 for i in range(len(nums)):
5 if nums[i] > 0 or i > 0 and nums[i] == nums[i-1]: continue
6 l, r = i+1, len(nums)-1
7 while l < r:
8 total = nums[i] + nums[l] + nums[r]
9 if total == 0:
10 res.append([nums[i], nums[l], nums[r]])
11 l, r = l+1, r-1
12 while l < len(nums) -1 and nums[l] == nums[l-1]:
13 l += 1
14 elif total > 0:
15 r -= 1
16 else:
17 l += 1
18 return res
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.