/**
* 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);
}
}
Category: interview
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]] Categories
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
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;
}
} Categories
CSS Margins Collapsing
CSS Vertical Margins of adjoining elements collapse vertically by default unless contained in a flexbox.
CSS Horizontal Margins never collapse.
Categories
Frog Jump – Java
This solution uses a HashMap
Format Currency
In case you want to implement a function to format currency instead of just using toLocaleString() then, you can use the following.
The array reference here is passed by value to the methods below. This is similar to what we usually see in case of Javascript.
call
The call() is a predefined Javascript function which can used to call a method of an object while passing it another object. For example, if you look at the following code, you will observe that the object being passed into the call() method replaces the this variable of the object whose method is being invoked.
In Javascript, when you pass a primitive data type like String or Int in Java to a function or a method, and a function modifies it, then this does not effect the actual data being passed. For example,
Categories
Floyd Warshall Algorithm
The Floyd Warshall Algorithm is used to find the shortest distance between all pairs in a weighted graph with positive or negative edges. It makes use of Dynamic Programming.
- If A, B, C are vertices, then this algorithm checks for the following
if (AC > AB + BC)
AC = AB + BC;