Month: August 2018

3Sum

Post author By Shiva Charan Devabhaktuni
Post date August 29, 2018

Time O(n2) & Memory O(1)

class Solution {
 public List < List < Integer >> threeSum(int[] nums) {
  int n = nums.length;
  List < List < Integer >> list = new ArrayList < List < Integer >> ();
     if(nums == null || nums.length<3)
        return list;
  Arrays.sort(nums);
  int left, right;
  for (int i = 0; i < n - 2; i++) {
   if(i > 0 && nums[i] == nums[i-1])
       continue;
   left = i + 1;
   right = n - 1;
   while (left < right) {
    if (nums[left] + nums[right] + nums[i] == 0) {
     List < Integer > temp = new ArrayList < Integer > ();
     temp.add(nums[i]);
     temp.add(nums[left]);
     temp.add(nums[right]);
     list.add(temp);
     left++;
     right--;
     while (nums[left] == nums[left - 1]) {
      left++;
     }
     while (left< right && nums[right] == nums[right + 1]) {
      right--;
     }
    } else if (nums[left] + nums[right] + nums[i]  > 0) {
     right--;
    } else
     left++;
   }
  }
  return list;
 }
}

Javascript ES6

const get3Sum = (arr) => {
  const results = [];
  arr.sort((a, b) => a - b);
  for (let i = 0; (i < arr.length - 2) && (arr[i] <= 0); i++) {
    if (i === 0 || arr[i] !== arr[i - 1]) {
      getPair(arr, i, results);
    }
  }
  return results;
};

const getPair = (arr, i, results) => {
  let left = i + 1;
  let right = arr.length - 1;
  while (left < right) {
    const sum = arr[i] + arr[left] + arr[right];
    if (sum === 0) {
      results.push([arr[i], arr[left++], arr[right--]]);
      while (arr[left - 1] == arr[left]) {
        left++;
      }
    } else if (sum < 0) {
      left++;
    } else if (sum > 0) {
      right--;
    }
  }
};

console.log(get3Sum([-1, 0, 1, 2, -1, -4]));
// [[-1 , 0, 1], [-1, -1, 2]]

Demo

Tags es6, google, java, javascript, js, leetcode, meta, optimal, phone screen, solution

interview

Trapping Rain Water

Post author By Shiva Charan Devabhaktuni
Post date August 29, 2018

Javascript (ES6)

/**
 * @param {number[]} height
 * @return {number}
 */
const trap = function(height) {
  const left = [];
  const right = [];
  let lmax = height[0];
  let rmax = height[height.length - 1];
  for (let i = 0; i < height.length; i++) {
    if (height[i] > lmax) {
      lmax = height[i];
    }
    left[i] = lmax;
    let j = height.length - i - 1;
    if (height[j] > rmax) {
      rmax = height[j];
    }
    right[j] = rmax;
  }
  let total = 0;
  for (let i = 0; i < height.length; i++) {
    total += Math.abs(height[i] - Math.min(left[i], right[i]));
  }
  return total;
};

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6

Demo

Java

Time: O(n)
Memory: O(n)


class Solution {
 public int trap(int[] height) {
  int n = height.length;
  if (n == 0)
   return 0;
  int[] left = new int[n];
  int[] right = new int[n];
  left[0] = height[0];
  right[n - 1] = height[n - 1];
  int j;
  for (int i = 1; i < n; i++) {
   left[i] = Math.max(left[i - 1], height[i]);
   right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
  }
  int area = 0;
  for (int i = 1; i < n - 1; i++) {
   area += Math.min(left[i], right[i]) - height[i];
  }
  return area;
 }
}