{"id":439,"date":"2025-06-29T16:39:20","date_gmt":"2025-06-29T11:09:20","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=439"},"modified":"2025-06-29T20:28:13","modified_gmt":"2025-06-29T14:58:13","slug":"3sum-leetcode-15","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/","title":{"rendered":"3Sum | Leetcode 15 | Explained in Python"},"content":{"rendered":"\n<p><strong>LeetCode #15 \u201c3Sum\u201d<\/strong> asks you to find <strong>all unique triplets<\/strong> <code>(i, j, k)<\/code> in an integer array such that<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"nums[i] + nums[j] + nums[k] == 0              (i &lt; j &lt; k)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">nums[i] + nums[j] + nums[k] == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">              (i &lt; j &lt; k)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>The answer must <strong>exclude duplicates<\/strong>, but the order within each triplet or across triplets does <strong>not<\/strong> matter.<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p><strong>Example<\/strong><br>Input <code>nums = [-1, 0, 1, 2, -1, -4]<\/code><br>Output <code>[[-1, -1, 2], [-1, 0, 1]]<\/code><\/p>\n<\/blockquote>\n\n\n\n<p>Why it matters: 3Sum is a classic interview favorite that highlights hashing, two-pointer techniques, and duplicate-handling strategies.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/3sum\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents\" id=\"ub_table-of-contents-3866ca5d-f862-4e90-a433-3e6dd74b8621\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"true\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">hide<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column \">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#0-brute-force-solution-triple-nested-loops\" style=\"\">Brute Force Solution (Triple Nested Loops)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#1-intuition-amp-approach\" style=\"\">Intuition &amp; Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#2-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#3-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#4-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#5-time-amp-space-complexity\" style=\"\">Time &amp; Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#6-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#7-better-solution-hash-set-per-fixed-index\" style=\"\">Better Solution (Hash-Set per Fixed Index)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#8-intuition-amp-approach\" style=\"\">Intuition &amp; Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#9-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#10-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#11-dry-run-short-example\" style=\"\">Dry Run (Short Example)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#12-time-amp-space-complexity\" style=\"\">Time &amp; Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#13-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#14-optimal-solution-sorting-two-pointers\" style=\"\">Optimal Solution (Sorting + Two Pointers)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#15-intuition-amp-approach\" style=\"\">Intuition &amp; Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#16-code-implementation\" style=\"\">Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#17-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#18-dry-run-classic-example\" style=\"\">Dry Run (Classic Example)<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#19-time-amp-space-complexity\" style=\"\">Time &amp; Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#20-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/3sum-leetcode-15\/#21-final-thoughts\" style=\"\">Final Thoughts<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-brute-force-solution-triple-nested-loops\">Brute Force Solution (Triple Nested Loops)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition-amp-approach\">Intuition &amp; Approach<\/h3>\n\n\n\n<p>The most literal idea is to <strong>test every possible triplet<\/strong>.<br>For each combination <code>(i, j, k)<\/code>:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Check if their sum is zero.<\/li>\n\n\n\n<li>Sort the triplet so <code>[a, b, c]<\/code> and <code>[b, a, c]<\/code> look identical.<\/li>\n\n\n\n<li>Store it in a <code>set<\/code> (of tuples) to eliminate duplicates automatically.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def threeSum(self, nums: List[int]) -&gt; List[List[int]]:\n        my_set = set()\n        n = len(nums)\n\n        # check all possible triplets\n        for i in range(n):\n            for j in range(i + 1, n):\n                for k in range(j + 1, n):\n                    # if the current triple sums to zero\n                    if nums[i] + nums[j] + nums[k] == 0:\n                        temp = [nums[i], nums[j], nums[k]]\n                        temp.sort()          # sort to avoid order duplicates\n                        my_set.add(tuple(temp))\n\n        # convert set of tuples back to list of lists for the answer\n        ans = [list(item) for item in my_set]\n        return ans\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">threeSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        my_set = <\/span><span style=\"color: #4EC9B0\">set<\/span><span style=\"color: #D4D4D4\">()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># check all possible triplets<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> k <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(j + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #6A9955\"># if the current triple sums to zero<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> nums[i] + nums[j] + nums[k] == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        temp = [nums[i], nums[j], nums[k]]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        temp.sort()          <\/span><span style=\"color: #6A9955\"># sort to avoid order duplicates<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        my_set.add(<\/span><span style=\"color: #4EC9B0\">tuple<\/span><span style=\"color: #D4D4D4\">(temp))<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># convert set of tuples back to list of lists for the answer<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans = [<\/span><span style=\"color: #4EC9B0\">list<\/span><span style=\"color: #D4D4D4\">(item) <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> item <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> my_set]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Three nested loops<\/strong> explore all <code>n \u00b7 (n-1) \u00b7 (n-2) \/ 6<\/code> triplets.<\/li>\n\n\n\n<li><strong>Sorting each hit<\/strong> guarantees <code>[2, -1, -1]<\/code> and <code>[-1, 2, -1]<\/code> merge into the same key.<\/li>\n\n\n\n<li><strong>Set<\/strong> ensures uniqueness; we convert back to list before returning.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Using <code>[-1, 0, 1]<\/code>:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th><code>(i,j,k)<\/code><\/th><th>Triple<\/th><th>Sum<\/th><th>Added?<\/th><th>Set Now<\/th><\/tr><\/thead><tbody><tr><td>0,1,2<\/td><td>-1,0,1<\/td><td>0<\/td><td>Yes<\/td><td>{[-1,0,1]}<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Every other combination fails or repeats, so the final answer is <code>[-1,0,1]<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-time-amp-space-complexity\">Time &amp; Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong> <code>O(n\u00b3)<\/code> \u2013 impractical beyond ~300 numbers.<\/li>\n\n\n\n<li><strong>Space:<\/strong> <code>O(t)<\/code> where <code>t<\/code> = #unique triplets (\u2264 <code>n\u00b3<\/code>) plus loop variables.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-conclusion\">Conclusion<\/h3>\n\n\n\n<p>Good for understanding the problem\u2019s essence, but far too slow for real data sets or interviews.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-better-solution-hash-set-per-fixed-index\">Better Solution (Hash-Set per Fixed Index)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-intuition-amp-approach\">Intuition &amp; Approach<\/h3>\n\n\n\n<p>Fix one number <strong><code>nums[i]<\/code><\/strong>, then the problem reduces to <strong>2Sum = -nums[i]<\/strong> inside the suffix <code>(i+1 \u2026 n-1)<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Maintain a <strong>hash set<\/strong> recording numbers we\u2019ve seen in the inner loop.<\/li>\n\n\n\n<li>If <code>third = - (nums[i] + nums[j])<\/code> is already in the set, we\u2019ve found a triplet.<\/li>\n\n\n\n<li>Again sort &amp; store in a global <code>set<\/code> to avoid duplicates.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def threeSum(self, nums: List[int]) -&gt; List[List[int]]:\n        n = len(nums)\n        result = set()  # stores unique sorted triplets\n\n        for i in range(n):\n            hashset = set()   # fresh set for each fixed i\n            for j in range(i + 1, n):\n                third = -(nums[i] + nums[j])  # value we need\n                if third in hashset:\n                    temp = [nums[i], nums[j], third]\n                    temp.sort()\n                    result.add(tuple(temp))\n                # add current nums[j] for future pairs\n                hashset.add(nums[j])\n\n        ans = list(result)\n        return ans\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">threeSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result = <\/span><span style=\"color: #4EC9B0\">set<\/span><span style=\"color: #D4D4D4\">()  <\/span><span style=\"color: #6A9955\"># stores unique sorted triplets<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            hashset = <\/span><span style=\"color: #4EC9B0\">set<\/span><span style=\"color: #D4D4D4\">()   <\/span><span style=\"color: #6A9955\"># fresh set for each fixed i<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                third = -(nums[i] + nums[j])  <\/span><span style=\"color: #6A9955\"># value we need<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> third <\/span><span style=\"color: #569CD6\">in<\/span><span style=\"color: #D4D4D4\"> hashset:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    temp = [nums[i], nums[j], third]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    temp.sort()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    result.add(<\/span><span style=\"color: #4EC9B0\">tuple<\/span><span style=\"color: #D4D4D4\">(temp))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #6A9955\"># add current nums[j] for future pairs<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                hashset.add(nums[j])<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans = <\/span><span style=\"color: #4EC9B0\">list<\/span><span style=\"color: #D4D4D4\">(result)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Outer loop<\/strong> picks every possible first element.<\/li>\n\n\n\n<li><strong>Inner loop<\/strong> simultaneously checks for complements while recording seen numbers in <code>hashset<\/code>.<\/li>\n\n\n\n<li>Each <code>hashset<\/code> is reset for a new <code>i<\/code> so only suffix elements pair with it.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-dry-run-short-example\">Dry Run (Short Example)<\/h3>\n\n\n\n<p>For <code>[-1, 0, 1, 2]<\/code>:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><code>i = 0<\/code> (<code>nums[i] = -1<\/code>)\n<ul class=\"wp-block-list\">\n<li><code>j = 1<\/code>: need <code>1<\/code>; <code>hashset = {0}<\/code> \u2192 not found<\/li>\n\n\n\n<li><code>j = 2<\/code>: need <code>0<\/code>; <code>hashset<\/code> has <code>0<\/code> \u2192 triplet <code>[-1, 0, 1]<\/code> stored<\/li>\n\n\n\n<li><code>j = 3<\/code>: need <code>-1<\/code>; not found<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Further <code>i<\/code> values may find more triplets (none in this short array).<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-time-amp-space-complexity\">Time &amp; Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong> <code>O(n\u00b2)<\/code> \u2013 outer <code>n<\/code> times inner <code>n<\/code>\/2 on average.<\/li>\n\n\n\n<li><strong>Space:<\/strong> <code>O(n)<\/code> \u2013 the per-iteration <code>hashset<\/code>.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-conclusion\">Conclusion<\/h3>\n\n\n\n<p>The hash-set technique crushes one loop and becomes feasible for arrays in the low-thousands, yet still incurs overhead from repeated set allocations.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"14-optimal-solution-sorting-two-pointers\">Optimal Solution (Sorting + Two Pointers)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-intuition-amp-approach\">Intuition &amp; Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Sort<\/strong> <code>nums<\/code>.<\/li>\n\n\n\n<li>For each index <code>i<\/code> (skipping duplicates):\n<ul class=\"wp-block-list\">\n<li>Target sum becomes <code>-nums[i]<\/code>.<\/li>\n\n\n\n<li>Use <strong>two pointers<\/strong> <code>j = i+1<\/code>, <code>k = n-1<\/code> to search the remaining sub-array for pairs adding to the target.<\/li>\n\n\n\n<li>On a hit, move both pointers inward while <strong>skipping duplicates<\/strong> to keep results unique.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p>Sorting lets identical numbers group together, simplifying duplicate elimination and enabling the two-pointer sweep in linear time per fixed <code>i<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"16-code-implementation\">Code Implementation<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def threeSum(self, nums: List[int]) -&gt; List[List[int]]:\n        ans = []\n        n = len(nums)\n        nums.sort()  # sort first for two-pointer technique\n\n        for i in range(n):\n            # skip duplicate fixed elements\n            if i != 0 and nums[i] == nums[i - 1]:\n                continue\n\n            # set up the two pointers\n            j = i + 1\n            k = n - 1\n\n            # move pointers toward each other\n            while j &lt; k:\n                total_sum = nums[i] + nums[j] + nums[k]\n\n                if total_sum &lt; 0:\n                    j += 1                     # need a larger sum\n                elif total_sum &gt; 0:\n                    k -= 1                     # need a smaller sum\n                else:\n                    # found a valid triplet\n                    temp = [nums[i], nums[j], nums[k]]\n                    ans.append(temp)\n\n                    # move both pointers and skip duplicates\n                    j += 1\n                    k -= 1\n                    while j &lt; k and nums[j] == nums[j - 1]:\n                        j += 1\n                    while j &lt; k and nums[k] == nums[k + 1]:\n                        k -= 1\n\n        return ans\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">threeSum<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        nums.sort()  <\/span><span style=\"color: #6A9955\"># sort first for two-pointer technique<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># skip duplicate fixed elements<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i != <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> nums[i] == nums[i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">continue<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># set up the two pointers<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            j = i + <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            k = n - <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># move pointers toward each other<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> j &lt; k:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                total_sum = nums[i] + nums[j] + nums[k]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> total_sum &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    j += <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">                     <\/span><span style=\"color: #6A9955\"># need a larger sum<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">elif<\/span><span style=\"color: #D4D4D4\"> total_sum &gt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    k -= <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">                     <\/span><span style=\"color: #6A9955\"># need a smaller sum<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #6A9955\"># found a valid triplet<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    temp = [nums[i], nums[j], nums[k]]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    ans.append(temp)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #6A9955\"># move both pointers and skip duplicates<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    j += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    k -= <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> j &lt; k <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> nums[j] == nums[j - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        j += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> j &lt; k <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> nums[k] == nums[k + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        k -= <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"17-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Sorting<\/strong> is the only extra cost and makes duplicate handling trivial.<\/li>\n\n\n\n<li><strong>Pointer Logic<\/strong>\n<ul class=\"wp-block-list\">\n<li><code>total_sum<\/code> too small \u21d2 increment <code>j<\/code> to pick a larger number.<\/li>\n\n\n\n<li><code>total_sum<\/code> too big \u21d2 decrement <code>k<\/code> for a smaller number.<\/li>\n\n\n\n<li>Hit \u21d2 record and move both pointers while skipping repeated values.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Duplicate-Skip Guard<\/strong> at the top ensures each distinct <code>nums[i]<\/code> is processed once.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"18-dry-run-classic-example\">Dry Run (Classic Example)<\/h3>\n\n\n\n<p>Sorted array: <code>[-4, -1, -1, 0, 1, 2]<\/code><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>i<\/th><th>nums[i]<\/th><th>j \/ k<\/th><th>total<\/th><th>Action \/ Triplet<\/th><th>ans<\/th><\/tr><\/thead><tbody><tr><td>0<\/td><td>-4<\/td><td>1\/5<\/td><td>-3<\/td><td>j++<\/td><td>\u2014<\/td><\/tr><tr><td><\/td><td><\/td><td>2\/5<\/td><td>-2<\/td><td>j++<\/td><td>\u2014<\/td><\/tr><tr><td><\/td><td><\/td><td>3\/5<\/td><td>-2<\/td><td>j++<\/td><td>\u2014<\/td><\/tr><tr><td><\/td><td><\/td><td>4\/5<\/td><td>-1<\/td><td>j++<\/td><td>\u2014<\/td><\/tr><tr><td>1<\/td><td>-1<\/td><td>2\/5<\/td><td>0<\/td><td>record <code>[-1,-1,2]<\/code>, move j,k<\/td><td><code>[-1,-1,2]<\/code><\/td><\/tr><tr><td><\/td><td><\/td><td>3\/4<\/td><td>0<\/td><td>record <code>[-1,0,1]<\/code><\/td><td><code>[-1,-1,2]<\/code>, <code>[-1,0,1]<\/code><\/td><\/tr><tr><td>2<\/td><td><em>skip<\/em><\/td><td>(duplicate)<\/td><td><\/td><td>\u2014<\/td><td>\u2014<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Pointers cross \u2192 finish.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"19-time-amp-space-complexity\">Time &amp; Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong> <code>O(n\u00b2)<\/code> overall (<code>O(n log n)<\/code> sort + <code>O(n\u00b2)<\/code> scan), but with a <strong>very low constant<\/strong> \u2013 fastest practical approach.<\/li>\n\n\n\n<li><strong>Space:<\/strong> <code>O(1)<\/code> extra (ignoring output) thanks to in-place sorting.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"20-conclusion\">Conclusion<\/h3>\n\n\n\n<p>The two-pointer strategy after sorting is the gold-standard answer in interviews: clean, efficient, and no hashing overhead. Mastering its duplicate-skip nuances is key to flawless implementation.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"21-final-thoughts\">Final Thoughts<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Brute<\/strong>: easiest to code, worst performance (<code>O(n\u00b3)<\/code>).<\/li>\n\n\n\n<li><strong>Better (Hash-set)<\/strong>: big speedup (<code>O(n\u00b2)<\/code>) but still rebuilds sets.<\/li>\n\n\n\n<li><strong>Optimal (Sort + Two Pointers)<\/strong>: same <code>O(n\u00b2)<\/code> time yet fastest in practice with <code>O(1)<\/code> extra space.<\/li>\n<\/ul>\n\n\n\n<p>Remember these three tiers, <strong>exhaustive, hashing, two-pointers<\/strong>, and you\u2019ll be ready for not only <strong>3Sum<\/strong> but a family of k-sum problems that build on these very ideas. Happy coding!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>LeetCode #15 \u201c3Sum\u201d asks you to find all unique triplets (i, j, k) in an integer array such that The answer must exclude duplicates, but the order within each triplet or across triplets does not matter. ExampleInput nums = [-1, 0, 1, 2, -1, -4]Output [[-1, -1, 2], [-1, 0, 1]] Why it matters: 3Sum<\/p>\n","protected":false},"author":1,"featured_media":440,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ub_ctt_via":"","footnotes":""},"categories":[3,5],"tags":[7,18,13],"class_list":{"0":"post-439","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-array","10":"tag-hard","11":"tag-two-pointers"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/3sum-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/439","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=439"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/439\/revisions"}],"predecessor-version":[{"id":471,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/439\/revisions\/471"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/440"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=439"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=439"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=439"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}