Java
LeetCode Problem-15 3Sum [Medium] (Java)
Welcome to the 15th coding challenge of leetcode problem series. My aim to provide more than just solutions. In each leetcode problem, expect a comprehensive breakdown of the code, a deep dive into the techniques employed, and a thoughtful exploration of why we opted for a specific approach. Join me as I embark on this journey of problem-solving, where each challenge serves as a stepping stone to honing our coding skills and making informed algorithmic choices. Welcome to a series that not only solves problems but also demystifies the thought processes behind effective coding solutions.
LeetCode Problem-15 3Sum
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
The algorithm used to solve the 3Sum problem is a combination of sorting and the two-pointer technique.
If you’re not familiar with the two-pointer technique, please refer to the article below (leetcode problem-1 Two Sum), where I’ve explained the concept and detailed the scenarios in which this technique can be effectively applied.
Overview of the approach:
✅ Sorting: The first step is to sort the input array. Sorting the array allows us to easily identify duplicate elements and skip them during the traversal. This is vital for ensuring that the result contains unique triplets. Without sorting, handling duplicates efficiently becomes more challenging and time-consuming.
✅ Two-Pointer Technique: After sorting, the algorithm uses a combination of two pointers (left and right) to traverse the array and find triplets that sum up to zero. The outer loop iterates through the array, and for each element, the inner loop uses two pointers to find a pair that sums to the negation of the current element.
👉 The left pointer starts just after the current element.
👉 The right pointer starts at the end of the array.
Depending on the sum of the triplet, the pointers are adjusted accordingly to move towards or away from each other.
✅ Handling Duplicates: The algorithm includes logic to skip duplicate elements to ensure that the result contains only unique triplets.
Java Code Solution
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// Sort the array to make the solution unique
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicate elements
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// Skip duplicate elements
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}Code Explanation Step by Step:
👉 The threeSum method takes an array of integers nums as input and returns a list of lists containing unique triplets that sum to zero.
👉 The array nums is sorted in ascending order using Arrays.sort(nums).
👉 The algorithm uses two nested loops. The outer loop for (int i = 0; i < nums.length - 2; i++) iterates through the array, and the inner loop (while (left < right)) uses two pointers (left and right) to find triplets.
👉 The condition i < nums.length - 2 in the outer loop is designed to ensure that there are at least two elements to the right of the current element at index i. This condition prevents unnecessary iterations when there are not enough elements remaining in the array to form a triplet
👉 We use a two-pointer technique with left and right pointers. The left pointer starts just after the current fixed element (nums[i]), and the right pointer starts at the end of the array.
int left = i + 1: This line ensures that theleftpointer is positioned to the right of the fixed element. Starting theleftpointer ati + 1ensures that we don't consider the same element twice and avoids duplicate triplets.int right = nums.length - 1: Therightpointer starts at the end of the array, which is the maximum possible position.
👉 Duplicate elements are skipped to ensure that the result contains only unique triplets.
👉 Inside the inner loop, the algorithm checks the sum of the triplet. If the sum is zero, the triplet is added to the result list. Duplicate elements are skipped again to avoid duplicate triplets in the result.
👉 The pointers (left and right) are adjusted based on the comparison of the sum. If the sum is less than zero, the left pointer is moved to the right; if the sum is greater than zero, the right pointer is moved to the left.
👉 The final list of unique triplets is returned as the result.
✅ Time Complexity:
👉 Sorting: The sorting step using Arrays.sort(nums) takes O(n log n) time, where "n" is the length of the input array.
👉 Two-Pointer Traversal: The two-pointer traversal inside the nested loop takes O(n) time, as both pointers move towards each other linearly.
The dominant factor is the sorting step, so the overall time complexity is O(n log n).
✅ Space Complexity:
👉 Result List (result): The space required for the result list is O(k), where "k" is the number of unique triplets that sum to zero.
👉 Other Variables: The additional space used by variables like i, left, right, and sum is constant, and it doesn't depend on the size of the input array.
Therefore, the overall space complexity is O(k), where “k” is the number of unique triplets in the result.
✔ What would be the space complexity if all possible triplets sum to zero?
In the worst case, where all possible triplets sum to zero, the space complexity would be O(n), where “n” is the length of the input array. This is because, every distinct triplet forms a valid solution and needs to be stored in the result list. In such a scenario, the result list would grow proportionally with the size of the input array.
“Congratulations on tackling this leetcode problem! Your dedication to sharpening your skills is truly commendable. Stay connected for upcoming leetocde problems in this series that will further fuel your passion for problem-solving. Remember, the journey of a coder is a continuous exploration. Happy coding, and see you in the next challenge!”
✅Similar leetcode problems 👇
👉LeetCode Problem-16 3Sum Closest [Medium]
👉Leetcode Problem-1 Two Sum
👉 Leetcode Problem-167 Two Sum II — Input Array Is Sorted [Medium]
❤️ Support & Engagement ❤️
❤ If you find this article informative and beneficial, please consider showing your appreciation by giving it a clap 👏👏👏, highlight it and replying on my story story. Feel free to share this article with your peers. Your support and knowledge sharing within the developer community are highly valued.
❤ Please share on social media
❤ Follow me on : Medium || LinkedIn
❤ Check out my other articles on Medium
❤ Subscribe to my newsletter 📧, so that you don’t miss out on my latest articles.
❤ If you enjoyed my article, please consider buying me a coffee ❤️ and stay tuned to more articles about java, technologies and AI. 🧑💻
