LeetCode - 4Sum

23 Jan 2018 • LeetCode(Second)

Question Definition

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

More …

LeetCode - 3Sum

23 Jan 2018 • LeetCode(Second)

Question Definition

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

More …

LeetCode - 3Sum Closest

23 Jan 2018 • LeetCode(Second)

Question Definition

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Java Solution

public int threeSumClosest(int[] nums, int target) {
    int closest = nums[0] + nums[1] + nums[2];
    int diff = Math.abs(closest - target);
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; ++i) {
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            int newDiff = Math.abs(sum - target);
            if (diff > newDiff) {
                diff = newDiff;
                closest = sum;
            }
            if (sum < target) ++left;
            else --right;
        }
    }
    return closest;
}

LeetCode - Unique Paths II

22 Jan 2018 • LeetCode(Second)

Question Definition

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example, There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

**Note: **m and n will be at most 100.

My Java Solution

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if(obstacleGrid.length == 0 || obstacleGrid[0].length == 0 || obstacleGrid[0][0] == 1)
        return 0;
    int[][] dp = new int[obstacleGrid.length + 1][obstacleGrid[0].length + 1];
    for(int i = 1; i < dp.length; i++){
        for(int j = 1; j < dp[i].length; j++){
            if(i == 1 && j == 1)
                dp[i][j] = 1;
            else if(obstacleGrid[i - 1][j - 1] == 1)
                dp[i][j] = 0;
            else{
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    return dp[obstacleGrid.length][obstacleGrid[0].length];
}