Thursday, August 20, 2015

Leetcode: 3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
For example, given nums = [-2, 0, 1, 3], and target = 2.
Return 2. Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]
Follow up:
Could you solve it in O(n2) runtime?
Understand the problem:
The problem looks quite similar to the 3-sum. Thus we could still sort the array first and use two pointers. 

The only thing needs to take special care of is how to move the pointers. There are two cases to handle: 
  -- If A[i] + A[j] + A[k] < target, which means the numbers between j and k are all less than target, because the array is sorted. Then we move the j pointer forward. 
  -- If A[i] + A[j] + A[k] >= target, we move k pointer backward.

Code (Java):
public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        
        int result = 0;
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] < target) {
                    result += (k - j);
                    j++;
                } else {
                    k--;
                }
            }
        }
        
        return result;
    }
}

9 comments:

  1. Why you used result += (k - j) instead of just result++ ?
    Can you explain the logic ?

    ReplyDelete
    Replies
    1. If A[i] + A[j] + A[k] < target, which means the numbers between j and k are all less than target, because the array is sorted. Then we move the j pointer forward.

      If it's less then the target, then that means it needs to be accounted for when you update the result count. If you don't, the algorithm won't hit those cases.

      Delete
    2. If A[i] + A[j] + A[k] < target, then we can fix i and j and move k in the range (j+1,k) to get all feasible triplets. so we add the total as (k-j) triplets

      Delete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Arrays.sort(array);

    for(int i = 0 ; i=target){
    break;
    }
    for(int j = i+1;j<array.length;j++){
    for(int k=j+1;k<array.length;k++){
    count++;
    sum=0;
    sum= array[i]+array[j]+array[k];
    if(sum < target){
    System.out.println("["+array[i]+","+array[j]+","+array[k]+"]");
    }else{

    break;
    }
    }// K
    }// J
    }// I
    System.out.println("count:"+count);

    ReplyDelete
  4. You can't sort. i < j < k .. means you need to retain the order of the indices! A more "brute force solution" with a duplicate removal mechanism is required.

    ReplyDelete
  5. the above code is wrong
    here is a code using backtracking
    res=[]
    nums=sorted([-2, 0, 1, 3])
    target=2
    def btr(com,k,n):
    #print(res)
    if(k==0 and sum(com)=target):
    return
    for i in range(n,len(nums)):
    btr(com+[nums[i]],k-1,i+1)
    btr([],3,0)
    print(res)

    ReplyDelete
  6. The above code is incorrect. It will fail most of the Test Cases

    ReplyDelete