CollegeStash

Author: Shiva Charan Devabhaktuni

  • String to Integer (atoi) – Java

    class Solution {
 public int myAtoi(String str) {
  int ret = 0;
  int i = 0;
  boolean negative = false;
  String retString = "";
  // Without using trim()
  // while(i<str.length() && str.charAt(i) == ' ')
  //     i++;
  str = str.trim();
  if (i >= str.length() || Character.isLetter(str.charAt(i)))
   return ret;
  if (str.charAt(i) == '-') {
   negative = true;
   i++;
  } else if (str.charAt(i) == '+') {
   i++;
  }
  while (i < str.length() && Character.isDigit(str.charAt(i))) {
   retString += str.charAt(i++);
  }
  if (retString != "") {
   try {
    ret = (negative ? -1 * Integer.parseInt(retString) : Integer.parseInt(retString));
   } catch (Exception e) {
    ret = (negative ? Integer.MIN_VALUE : Integer.MAX_VALUE);
   }
  }
  return ret;
 }
}

  • Merge Intervals

    Javascript (ES6)

    /**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
const merge = (intervals) => {
  intervals.sort((a, b) => a[0] - b[0]);
  const ret = [];
  let prev = null;
  for (const interval of intervals) {
    if (prev != null) {
      if (interval[0] > prev[1]) {
        ret.push(prev);
        prev = interval;
      } else {
        // Merge case.
        prev[1] = Math.max(interval[1], prev[1]);
      }
    } else {
      prev = interval;
    }
  }
  if (prev !== null) {
    ret.push(prev);
  }
  return ret;
};

console.log(merge([
  [1, 3],
  [2, 6],
  [8, 10],
  [15, 18]
])); // [[1,6],[8,10],[15,18]]

    Demo

    If  “n” is the length of the input list, then the “Time Complexity”  is O(nlogn).

    /**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */

class Solution {
 public List < Interval > merge(List < Interval > intervals) {
  // Sort the input list by the start times.
  Collections.sort(intervals, (a, b) -> a.start - b.start);
  List < Interval > ret = new ArrayList < Interval > ();
  Interval prev = null;
  for (Interval curr: intervals) {
   if (prev == null) {
    prev = curr;
   } else {
    if (curr.start <= prev.end) {
     prev.end = Math.max(curr.end, prev.end);
    } else {
     ret.add(prev);
     prev = curr;
    }
   }
  }
  if (prev != null) {
   ret.add(prev);
  }
  return ret;
 }
}

  • Product of Array Except Self – Java

    Time – O(n)
    Space – 0(1)  – Neglecting the output array that is expected to be returned.

    class Solution {
 public int[] productExceptSelf(int[] nums) {
  int n = nums.length;
  int[] output = new int[n];
  int temp = 1;
  // product from left to right excluding nums[i]
  for (int i = 0; i < n; i++) {
   output[i] = temp;
   temp *= nums[i];
  }
  temp = 1;
  // product from right to left excluding nums[i]
  for (int i = n - 1; i >= 0; i--) {
   output[i] *= temp;
   temp *= nums[i];
  }
  return output;
 }
}

  • Copy List with Random Pointer (Reference) – Java

    This method doesn’t use a HashMap.

    Copy List with Random Pointer

    /**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
 public RandomListNode copyRandomList(RandomListNode head) {
  if (head == null)
   return null;
  // Step 1 - Store copy in next
  RandomListNode n = head;
  while (n != null) {
   RandomListNode c = new RandomListNode(n.label);
   c.next = n.next;
   n.next = c;
   n = c.next;
  }
  // Step 2 - Copy Random reference
  n = head;
  while (n != null) {
   if (n.random != null) {
    n.next.random = n.random.next;
   }
   n = n.next.next;
  }
  // Step 3 - Break references
  n = head;
  RandomListNode ret = head.next;
  while (n != null) {
   RandomListNode copy = n.next;
   n.next = copy.next;
   if (n.next != null) {
    copy.next = n.next.next;
   }
   n = n.next;
  }
  return ret;
 }
}

     

     

  • Flatten Binary Tree to Linked List – Java

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public void flatten(TreeNode root) {
  moveLeftToRight(root);
 }

 public TreeNode moveLeftToRight(TreeNode root) {
  if (root == null)
   return null;
  TreeNode last = null;
  TreeNode right = root.right;
  if (root.left != null) {
   root.right = root.left;
   root.left = null;
   last = moveLeftToRight(root.right);
   last.right = right;
  }
  if (right != null) {
   last = moveLeftToRight(right);
  }
  return (last != null ? last : root);
 }
}

  • 3Sum

    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

  • Trapping Rain Water

    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 Complexity: O(n)
    Space Complexity: 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;
 }
}

  • CSS Margins Collapsing

    CSS Vertical Margins  of adjoining elements collapse vertically by default unless contained in a flexbox.

    CSS Horizontal Margins never collapse.

    (more…)

  • Frog Jump – Java

    This solution uses a HashMap (more…)

  • Flexbox – Div at end of row

    The following lines of code demonstrate how to align a div at the end of the flexbox row when you want to display the rest of the them at the start.
    flexbox
    (more…)