- Published on
Three Way to partition an Array
- Authors
- Name
- Rakesh Yadav
- @jsbugpost
Given an array containing N
integers, and an number S
denoting a target sum
.
Find all distinct integers that can add up to form target sum. The numbers in each triplet should be ordered in ascending order, and triplets should be ordered too.
Return empty array if no such triplet exists.
Note: For Simplicity we taking sum=0
always.
For exact problem visit Leetcode Link;
Sample Input Output
Input: nums = [-1, 0, 1, 2, -1, -4]Output: [ [-1, -1, 2], [-1, 0, 1],]
Input: nums = []Output: []
Input: [0, 0, 0, 0, 0]Output: [0, 0, 0]
Solution Approach
There are many approach to solve this problem.
-
First: Generate all triplet and check if their sum is equal to
sum
.Time Complexity: O(N)
Space Complexity: O(1)
Where
N
is length of input array. -
Second: For every element of array
i
check if there is a pair whose sum issum-nums[i]
. We can check pair sum inO(N)
usinghashing
. Handling duplicate number will make this implementation complecated and also it will takeO(N)
extra space.Time Complexity: O(N*N)
Space Complexity: O(N)
-
Third(Preferred for Above Problem): In this solution we will opimize the way we are searching
Pair Sum
by usingsorting
andTwo Pointer
approach.- Sort the array TC:
O(NlogN)
. - Iterate from
i=0
ton-1
and for every element of arrayi
check if there is pair betweeni+1
ton-1
whose sum issum - nums[i]
. - If there any unique pair satisfy our condition will be pushed in
ans
array. - For checking pair we used two pointer approach.
Time Complexity: O(N*N)
Space Complexity: O(1)
- Sort the array TC:
Javascript Implementation
/** * @param {number[]} nums * @return {number[][]} */var threeSum = function (nums) { const ans = [] // to store all triplets nums.sort((a, b) => a - b) // Sorted array in ascending order
function getPairs(i, j, n) { while (i < j) { if (nums[i] + nums[j] === n) { ans.push([-n, nums[i++], nums[j++]]) } else if (nums[i] + nums[j] < n) { i++ } else { j-- } // To Avoid duplicate Triplets while (nums[i + 1] === nums[i]) { i++ } } }
for (let i = 0; i < nums.length - 2; i++) { // This if check will make sure we dont calculte triplet for same number if (i === 0 || nums[i] !== nums[i - 1]) { getPairs(i + 1, nums.length - 1, -nums[i]) } }
return ans}