{"id":442,"date":"2025-06-29T16:47:58","date_gmt":"2025-06-29T11:17:58","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=442"},"modified":"2025-06-29T16:47:59","modified_gmt":"2025-06-29T11:17:59","slug":"4sum-leetcode-18","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/4sum-leetcode-18\/","title":{"rendered":"4Sum | Leetcode 18 | Explained in Python"},"content":{"rendered":"\n<p>The <strong>LeetCode \u201c4Sum\u201d<\/strong> problem asks you to find <strong>all unique quadruplets<\/strong> in an integer array <code>nums<\/code> 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[a] + nums[b] + nums[c] + nums[d] == target     (where a &lt; b &lt; c &lt; d)\" 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[a] + nums[b] + nums[c] + nums[d] == target     (where a &lt; b &lt; c &lt; d)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>Key details:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Unique<\/strong> means no duplicate quadruplets in the output, regardless of order inside each four-tuple.<\/li>\n\n\n\n<li>Elements may contain duplicates, but index positions must be distinct.<\/li>\n\n\n\n<li>Output quadruplets can appear in any order.<\/li>\n<\/ul>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/4sum\/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\n<h3 class=\"wp-block-heading\" id=\"0-quick-example\">Quick Example<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Input<\/th><th>Output (any order)<\/th><\/tr><\/thead><tbody><tr><td><code>nums = [1, 0, -1, 0, -2, 2]<\/code>, <code>target = 0<\/code><\/td><td><code>[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Think of it as the bigger sibling of 2Sum and 3Sum: you still balance numbers to hit a target total, but now with four picks and stricter duplicate handling.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"1-brute-force-solution-four-nested-loops\">Brute Force Solution (Four Nested Loops)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<p>The most direct route is to <strong>try every possible combination<\/strong> of four indices:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Loop across indices <code>i &lt; j &lt; k &lt; l<\/code>.<\/li>\n\n\n\n<li>Compute their sum; if it equals <code>target<\/code>, you found a hit.<\/li>\n\n\n\n<li>Sort the quadruplet (to get a canonical form) and store it in a <code>set<\/code> so duplicates collapse automatically.<\/li>\n<\/ol>\n\n\n\n<p>The logic is crystal clear, but performance quickly becomes prohibitive: checking every quadruplet is <code>O(n\u2074)<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-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=\"def fourSum(self, nums: List[int], target: int) -&gt; List[List[int]]:\n    n = len(nums)\n    if n &lt; 4:\n        return []\n    \n    my_set = set()  # set ensures uniqueness\n\n    # try all possible quadruplets\n    for i in range(0, n):\n        for j in range(i + 1, n):\n            for k in range(j + 1, n):\n                for l in range(k + 1, n):\n                    total = nums[i] + nums[j] + nums[k] + nums[l]\n\n                    if total == target:              # hit the target\n                        temp = [nums[i], nums[j], nums[k], nums[l]]\n                        temp.sort()                  # canonical order\n                        my_set.add(tuple(temp))      # store as tuple in the set\n\n    # convert each tuple back to list\n    result = []\n    for ans in my_set:\n        result.append(list(ans))\n\n    return result\" 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\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">fourSum<\/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\">], <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">: <\/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\">    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> n &lt; <\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> []<\/span><\/span>\n<span class=\"line\"><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 style=\"color: #6A9955\"># set ensures uniqueness<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># try all possible quadruplets<\/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\">(<\/span><span style=\"color: #B5CEA8\">0<\/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: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> l <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(k + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    total = nums[i] + nums[j] + nums[k] + nums[l]<\/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 == target:              <\/span><span style=\"color: #6A9955\"># hit the target<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        temp = [nums[i], nums[j], nums[k], nums[l]]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        temp.sort()                  <\/span><span style=\"color: #6A9955\"># canonical order<\/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 style=\"color: #6A9955\"># store as tuple in the set<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># convert each tuple back to list<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    result = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> ans <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> my_set:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result.append(<\/span><span style=\"color: #4EC9B0\">list<\/span><span style=\"color: #D4D4D4\">(ans))<\/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\"> result<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Four nested loops<\/strong> generate each unique index combination exactly once.<\/li>\n\n\n\n<li><strong>Sorting and a set<\/strong> together erase permutations like <code>[1,0,-1,2]<\/code> vs <code>[-1,1,0,2]<\/code>.<\/li>\n\n\n\n<li>Finally, the set of tuples is flattened to a list of lists for the return value.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run-tiny-example\">Dry Run (Tiny Example)<\/h3>\n\n\n\n<p>For <code>nums = [2, 2, 2, 2]<\/code>, <code>target = 8<\/code>:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Only one quadruplet exists: indices <code>(0,1,2,3)<\/code>.<\/li>\n\n\n\n<li>Sum = <code>2+2+2+2 = 8<\/code> \u2192 store <code>(2,2,2,2)<\/code>.<\/li>\n\n\n\n<li>After loops end, <code>result = [[2,2,2,2]]<\/code>.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong> <code>O(n\u2074)<\/code> \u2013 extremely slow for <code>n > 100<\/code>.<\/li>\n\n\n\n<li><strong>Space:<\/strong> Up to <code>O(q)<\/code> for <code>q<\/code> unique quadruplets (worst\u2010case <code>\u2248 n\u2074\/24<\/code>).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-conclusion\">Conclusion<\/h3>\n\n\n\n<p>Great for conceptual clarity, terrible for large inputs\u2014so let\u2019s optimize!<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-better-solution-hashing-inside-three-loops\">Better Solution (Hashing Inside Three Loops)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<p>Fix the first two numbers with an outer-pair <code>(i, j)<\/code>.<br>Now you need a <strong>2Sum<\/strong> on the remaining suffix that equals <code>target \u2013 (nums[i]+nums[j])<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>For each <code>(i, j)<\/code>, walk the rest of the array with index <code>k<\/code>.<\/li>\n\n\n\n<li>Maintain a <strong>hash set<\/strong> of numbers already seen in this inner loop.<\/li>\n\n\n\n<li>If the needed <code>fourth = target - (nums[i] + nums[j] + nums[k])<\/code> is in the set, you have a quadruplet.<\/li>\n\n\n\n<li>Again sort and store in a global <code>set<\/code> to kill duplicates.<\/li>\n<\/ul>\n\n\n\n<p>This trims one whole loop and crashes runtime down to <code>O(n\u00b3)<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-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=\"def fourSum(self, nums: List[int], target: int) -&gt; List[List[int]]:\n    n = len(nums)\n    if n &lt; 4:\n        return []\n    \n    my_set = set()  # stores unique quadruplets\n\n    # \ud83d\udc6b fix first two indices\n    for i in range(0, n):\n        for j in range(i + 1, n):\n            hash_set = set()  # tracks needed fourth numbers\n            # scan remaining indices for third element\n            for k in range(j + 1, n):\n                fourth = target - (nums[i] + nums[j] + nums[k])\n\n                if fourth in hash_set:           # found match\n                    temp = [nums[i], nums[j], nums[k], fourth]\n                    temp.sort()\n                    my_set.add(tuple(temp))\n\n                # add current third element for future matches\n                hash_set.add(nums[k])\n\n    # convert to required list format\n    result = [list(ans) for ans in my_set]\n    return result\" 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\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">fourSum<\/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\">], <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">: <\/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\">    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> n &lt; <\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> []<\/span><\/span>\n<span class=\"line\"><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 style=\"color: #6A9955\"># stores unique quadruplets<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># \ud83d\udc6b fix first two indices<\/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\">(<\/span><span style=\"color: #B5CEA8\">0<\/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\">            hash_set = <\/span><span style=\"color: #4EC9B0\">set<\/span><span style=\"color: #D4D4D4\">()  <\/span><span style=\"color: #6A9955\"># tracks needed fourth numbers<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># scan remaining indices for third element<\/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\">                fourth = target - (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\"> fourth <\/span><span style=\"color: #569CD6\">in<\/span><span style=\"color: #D4D4D4\"> hash_set:           <\/span><span style=\"color: #6A9955\"># found match<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    temp = [nums[i], nums[j], nums[k], fourth]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    temp.sort()<\/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\"># add current third element for future matches<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                hash_set.add(nums[k])<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># convert to required list format<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    result = [<\/span><span style=\"color: #4EC9B0\">list<\/span><span style=\"color: #D4D4D4\">(ans) <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> ans <\/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\"> result<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Outer double loop<\/strong> picks a distinct pair.<\/li>\n\n\n\n<li><strong>Inner loop + hash set<\/strong> solves a 2Sum in linear time on the suffix.<\/li>\n\n\n\n<li>Each <code>(i, j)<\/code> gets its own <code>hash_set<\/code>, avoiding cross-pair contamination.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-dry-run-mini-input\">Dry Run (Mini Input)<\/h3>\n\n\n\n<p><code>nums = [1,1,2,2]<\/code>, <code>target = 6<\/code><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><code>(i=0, j=1)<\/code> \u2192 need two numbers summing to <code>4<\/code>.<\/li>\n\n\n\n<li><code>k=2<\/code> (<code>nums[k]=2<\/code>), <code>fourth=2<\/code>, not in set \u2192 add 2.<\/li>\n\n\n\n<li><code>k=3<\/code> (<code>nums[k]=2<\/code>), <code>fourth=2<\/code> <em>is<\/em> in set \u2192 store <code>[1,1,2,2]<\/code>.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong> <code>O(n\u00b3)<\/code> \u2013 three effective loops.<\/li>\n\n\n\n<li><strong>Space:<\/strong> <code>O(n)<\/code> extra for the transient <code>hash_set<\/code>.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-conclusion\">Conclusion<\/h3>\n\n\n\n<p>Big improvement over brute force, yet still sluggish for <code>n \u2248 1000<\/code>. We can push further by sorting and sliding pointers.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"15-optimal-solution-sort-two-pointer-technique\">Optimal Solution (Sort + Two-Pointer Technique)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"16-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Sort<\/strong> <code>nums<\/code> to group duplicates and enable two-pointer sweeps.<\/li>\n\n\n\n<li>Pick first two indices <code>(i, j)<\/code> with nested loops, <strong>skipping duplicates<\/strong>.<\/li>\n\n\n\n<li>For the remaining sub-array, run <strong>two pointers<\/strong> <code>k<\/code> (left) and <code>l<\/code> (right).<\/li>\n\n\n\n<li>Compare their four-number sum to <code>target<\/code> and move pointers accordingly:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Sum <strong>&lt; target<\/strong> \u279c increase <code>k<\/code> to make it larger.<\/li>\n\n\n\n<li>Sum <strong>> target<\/strong> \u279c decrease <code>l<\/code> to make it smaller.<\/li>\n\n\n\n<li>Sum <strong>== target<\/strong> \u279c record quadruplet, shift both pointers, and <strong>skip duplicate values<\/strong>.<\/li>\n<\/ul>\n\n\n\n<p>This gives <code>O(n\u00b3)<\/code> time but with a tiny constant, plus only <code>O(1)<\/code> auxiliary space.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"17-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=\"def fourSum(self, nums: List[int], target: int) -&gt; List[List[int]]:\n    n = len(nums)\n    ans = []\n    nums.sort()  # Step 1: sort to simplify duplicates\n\n    # \ud83d\udeb6\u200d\u2642\ufe0f Step 2: pick first two numbers\n    for i in range(0, n):\n        if i &gt; 0 and nums[i] == nums[i - 1]:  # skip duplicates for i\n            continue\n\n        for j in range(i + 1, n):\n            if j &gt; i + 1 and nums[j] == nums[j - 1]:  # skip duplicates for j\n                continue\n\n            # Step 3: two-pointer search for remaining two\n            k = j + 1               # left pointer\n            l = n - 1               # right pointer\n\n            while k &lt; l:\n                total = nums[i] + nums[j] + nums[k] + nums[l]\n\n                if total == target:\n                    ans.append([nums[i], nums[j], nums[k], nums[l]])\n                    k += 1\n                    l -= 1\n\n                    # skip duplicate values for k\n                    while k &lt; l and nums[k] == nums[k - 1]:\n                        k += 1\n                    # skip duplicate values for l\n                    while l &gt; k and nums[l] == nums[l + 1]:\n                        l -= 1\n\n                elif total &lt; target:\n                    k += 1           # need a larger sum\n\n                else:\n                    l -= 1           # need a smaller sum\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\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">fourSum<\/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\">], <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">: <\/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\">    ans = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    nums.sort()  <\/span><span style=\"color: #6A9955\"># Step 1: sort to simplify duplicates<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># \ud83d\udeb6\u200d\u2642\ufe0f Step 2: pick first two numbers<\/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\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i &gt; <\/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 style=\"color: #6A9955\"># skip duplicates for i<\/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: #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\">if<\/span><span style=\"color: #D4D4D4\"> j &gt; i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> <\/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 style=\"color: #6A9955\"># skip duplicates for j<\/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\"># Step 3: two-pointer search for remaining two<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            k = j + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">               <\/span><span style=\"color: #6A9955\"># left pointer<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            l = n - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">               <\/span><span style=\"color: #6A9955\"># right pointer<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> k &lt; l:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                total = nums[i] + nums[j] + nums[k] + nums[l]<\/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 == target:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    ans.append([nums[i], nums[j], nums[k], nums[l]])<\/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\">                    l -= <\/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\"># skip duplicate values for k<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> k &lt; l <\/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 style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #6A9955\"># skip duplicate values for l<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> l &gt; k <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> nums[l] == nums[l + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        l -= <\/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\">elif<\/span><span style=\"color: #D4D4D4\"> total &lt; target:<\/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 larger sum<\/span><\/span>\n<span class=\"line\"><\/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\">                    l -= <\/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>\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=\"18-code-explanation\">Code Explanation<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Sorting<\/strong> arranges duplicates consecutively, letting simple pointer checks skip repeats.<\/li>\n\n\n\n<li><strong>Pointer Dynamics:<\/strong> <code>k<\/code> moves rightward for larger sums; <code>l<\/code> moves leftward for smaller.<\/li>\n\n\n\n<li><strong>Duplicate Guards<\/strong> after each pointer shift guarantee every quadruplet appears only once.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"19-dry-run-key-steps\">Dry Run (Key Steps)<\/h3>\n\n\n\n<p>Sorted <code>nums = [-2, -1, 0, 0, 1, 2]<\/code>, <code>target = 0<\/code><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>i<\/th><th>j<\/th><th>k \/ l<\/th><th>Total<\/th><th>Action \/ Output<\/th><th>ans<\/th><\/tr><\/thead><tbody><tr><td>0<\/td><td>1<\/td><td>2 \/ 5<\/td><td>-1<\/td><td>k++<\/td><td>\u2014<\/td><\/tr><tr><td><\/td><td><\/td><td>3 \/ 5<\/td><td>-1<\/td><td>k++<\/td><td>\u2014<\/td><\/tr><tr><td><\/td><td><\/td><td>4 \/ 5<\/td><td>0<\/td><td>record <code>[-2,-1,1,2]<\/code><\/td><td><code>[-2,-1,1,2]<\/code><\/td><\/tr><tr><td>0<\/td><td>2<\/td><td>\u2026<\/td><td>\u2026<\/td><td>eventually <code>[-2,0,0,2]<\/code><\/td><td><code>[-2,-1,1,2]<\/code>, <code>[-2,0,0,2]<\/code><\/td><\/tr><tr><td>1<\/td><td>2<\/td><td>\u2026<\/td><td>\u2026<\/td><td>later <code>[-1,0,0,1]<\/code><\/td><td>plus <code>[-1,0,0,1]<\/code><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Pointers skip duplicates along the way, producing exactly three unique quadruplets.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"20-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong> <code>O(n\u00b3)<\/code> (dominated by the double loop \u00d7 linear scan) with a small constant; plus <code>O(n log n)<\/code> for the sort.<\/li>\n\n\n\n<li><strong>Space:<\/strong> <code>O(1)<\/code> extra (ignoring output list).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"21-conclusion\">Conclusion<\/h3>\n\n\n\n<p>Sorting + two pointers is the standard, interview-ready answer: concise, fast in practice, and memory-friendly. Master its duplicate-skipping pattern for perfectly clean results.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"22-final-thoughts-\">Final Thoughts \ud83c\udfaf<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Brute Force (O(n\u2074))<\/strong> \u2013 intuitive starter, but rarely acceptable.<\/li>\n\n\n\n<li><strong>Better (Hash-set, O(n\u00b3))<\/strong> \u2013 removes one loop, still heavy.<\/li>\n\n\n\n<li><strong>Optimal (Sort + Two Pointers, O(n\u00b3) with tiny constant)<\/strong> \u2013 passes competitive constraints with minimal space.<\/li>\n<\/ul>\n\n\n\n<p>By climbing this ladder, <strong>exhaustive \u2192 hashing \u2192 pointer squeezing<\/strong>, you\u2019ll gain insight not just into <em>4Sum<\/em> but the entire family of k-Sum challenges. Happy algorithm hacking!<\/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:\/\/www.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\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The LeetCode \u201c4Sum\u201d problem asks you to find all unique quadruplets in an integer array nums such that Key details: Here&#8217;s the [Problem Link] to begin with. Quick Example Input Output (any order) nums = [1, 0, -1, 0, -2, 2], target = 0 [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0,<\/p>\n","protected":false},"author":1,"featured_media":444,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ub_ctt_via":"","footnotes":""},"categories":[3,5],"tags":[7,18,9,13],"class_list":{"0":"post-442","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-hash-table","12":"tag-two-pointers"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/4sum-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\/442","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=442"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/442\/revisions"}],"predecessor-version":[{"id":445,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/442\/revisions\/445"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/444"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=442"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=442"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=442"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}