Python solution with detailed explanation


  • 0
    G

    Solution

    3Sum Smaller https://leetcode.com/problems/3sum-smaller/

    1. Brute force is N^3 and N^2 is the optimized algorithm which uses two pointer technique.
    2. Look at the analysis for https://leetcode.com/problems/3sum-closest/. Understand how the two pointer scheme works and why we move j to the right and k to the left. The intuition is that based on the comparision with target sum, we can skip portions.
    3. A great explanation is available here: https://leetcode.com/articles/3sum-smaller/. First reduce the problem to 2SUM and then apply binary search or 2 pointer solution.
    4. In binary search, the 2 SUM condition is nums[i]+nums[j] < target. This means we want to find all the nums[j] which satisfy nums[j] < target-nums[i]. This means we want to find the rank of target-nums[i]. use the code for rank from notes.
    5. Once you understand that well, there is one line of code required to make this work.
                while j < k:
                    if nums[i]+nums[j]+nums[k] < target:
                        triplets = triplets + (k-j)
    
    class Solution(object):
        def threeSumSmaller(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            nums.sort()
            triplets = 0
            for i in range(len(nums)):
                j,k = i+1, len(nums)-1
                while j < k:
                    if nums[i]+nums[j]+nums[k] < target:
                        triplets = triplets + (k-j)
                        j = j+1
                    else:
                        k = k-1
            return triplets
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.