Skip to main content

Leetcode 16: 3Sum Closest

 

1. Problem Statement (Simple Explanation):


You are given:

  • An integer array nums of length n

  • An integer target

You must choose three distinct indices i, j, k such that the sum:

            sum = nums[i] + nums[j] + nums[k]

is as close as possible to target.

Return:

  • The sum of the three integers (not the triplet itself).

You are guaranteed that exactly one best answer exists.


2. Examples:


Example 1:

Input: nums = [-1, 2, 1, -4], target = 1

All possible triplet sums (showing the relevant ones):

  • -1 + 2 + 1 = 2

  • -1 + 2 + (-4) = -3

  • -1 + 1 + (-4) = -4

  • 2 + 1 + (-4) = -1

Differences from target 1:

  • |2 - 1| = 1

  • |-3 - 1| = 4

  • |-4 - 1| = 5

  • |-1 - 1| = 2

Closest is 2.

Output: 2


Example 2:

Input: nums = [0,0,0], target = 1

Only triplet sum:

  • 0 + 0 + 0 = 0

Difference:

  • |0 - 1| = 1

Output: 0


3. Approach 1 – Brute Force (O(n³), Just for Understanding):


  • Try all triplets (i, j, k) with i < j < k.

  • Compute each sum.

  • Track the one with minimum |sum - target|.

Time complexity:

  • O(n3), which is too slow for n up to 500 (approx 20M triplets).

We need a better approach.


4. Approach 2 – Sort + Two Pointers (O(n²), Recommended):


This is very similar in structure to 3Sum, but instead of finding exact sum == 0, we track the closest sum to target.


Intuition:


  1. Sort the array nums.

  2. Fix one index i as the first element.

  3. Use two pointers:

    • left = i + 1

    • right = n - 1

  4. Compute:

    • sum = nums[i] + nums[left] + nums[right]

  5. Compare |sum - target| with current best difference:

    • If smaller → update the best sum.

  6. Adjust pointers:

    • If sum < target, we need a bigger sum → move left++.

    • If sum > target, we need a smaller sum → move right--.

    • If sum == target → exactly closest possible → return sum immediately.

No need to worry about duplicate triplets, because we only return the sum, not the list of triplets.


Algorithm (Step-by-Step):


  1. Sort nums.

  2. Initialize:

    • closestSum = nums[0] + nums[1] + nums[2] (first possible triplet).

  3. For each i from 0 to n - 3:

    • left = i + 1

    • right = n - 1

    • While left < right:

      • sum = nums[i] + nums[left] + nums[right]

      • If |sum - target| < |closestSum - target|:

        • Update closestSum = sum.

      • If sum < target:

        • Move left++

      • Else if sum > target:

        • Move right--

      • Else:

        • Return target (exact match).

  4. After the loops, return closestSum.


Pseudo-code (Sort + Two Pointers):


Complexity:

  • Sorting: O(n*logn)

  • Outer loop i: O(n)

  • Inner two-pointer: O(n)

Overall:

  • Time: O(n2)

  • Space: O(1) extra (in-place sort aside)

This is optimal for this problem.


5. Java code:



6.  C code:



7. C++ code:



8. Python code:


9. JavaScript code:




<<<PREV

Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more