Tree

function TreeNode(val, left, right) {
      this.val = (val===undefined ? 0 : val)
      this.left = (left===undefined ? null : left)
      this.right = (right===undefined ? null : right)
 }

Traversals. Depth-first: Inorder, pre-order, post-order. Bread-first.

Set all of the O to – across the board

For each side find adjacent – and change them to Os using flash flood algorithm

Change all of the remaining – to X

The complexity of the above solution is O(m*n)

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {   
     for (let i=0; i< board.length; i++) {
        for (let j=0; j< board[i].length; j++){ 
            if (board[i][j] == 'O') {
                board[i][j] = '-';
            }
        }
     }
       
    //left side
    for (let i=0; i< board.length; i++) {
        floodFill(board, i, 0, '-', 'O' );
    }
      //right side
    for (let i=0; i< board.length; i++) {
        floodFill(board, i, board[i].length-1, '-', 'O' );
    }
        //top side
    for (let j=0; j< board[0].length; j++) {
        floodFill(board, 0, j, '-', 'O' );
    }
    //bottom side
    for (let j=0; j< board[0].length; j++) {
        floodFill(board, board.length-1, j, '-', 'O' );
    }
    
     for (let i=0; i< board.length; i++) {
        for (let j=0; j< board[i].length; j++){ 
            if (board[i][j] == '-') {
                board[i][j] = 'X';
            }
        }
     }
    
    return board;
};


var floodFill = function(board, i, j, prevVal, newVal) {
    if (i<0 || j<0 || i>=board.length || j>=board[0].length) {
        return;
    }
    
    if (prevVal != board[i][j]) {
        return;
    }
     
    board[i][j] = newVal;
   
    //check north
     floodFill(board, i-1,j, prevVal, newVal);
    //check east
    floodFill(board, i,j+1, prevVal, newVal);
    //check south 
    floodFill(board, i+1,j, prevVal, newVal);
    //check west
    floodFill(board, i,j-1, prevVal, newVal);
  
}

A list of problems that will let you learn dynamic programming

Maximum Subarray

Can be solved with Kadane algorithm

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    //Kadanes algorithm
    /*
        Initialize:
    max_so_far = INT_MIN
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
  (c) if(max_ending_here < 0)
            max_ending_here = 0
return max_so_far
    */
    
    let maxSoFar = nums[0];
    let minSoFar = nums[0];
    let maxEndingHere = 0;
    
    for (let i=0; i<nums.length; i++) {
        maxEndingHere = maxEndingHere + nums[i];
        if (maxSoFar < maxEndingHere) {
            maxSoFar = maxEndingHere;
        } 
        if (maxEndingHere < 0) {
            maxEndingHere = 0;
        }
    }
    return maxSoFar;
};

Maximum Product Subarray

Instead of using one variable to store the max we can use two variables to store max and min and flip them whenever we would meet a negative value

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let maxProduct = nums[0];
    let maxSoFar = nums[0];
    let minSoFar = nums[0];
    
    for (let i=1; i< nums.length; i++) {
        if (nums[i] < 0) { //swap
            let temp = minSoFar;
            minSoFar = maxSoFar;
            maxSoFar = temp;
        }
        
        minSoFar = Math.min(nums[i], minSoFar * nums[i]);
        maxSoFar = Math.max(nums[i], maxSoFar * nums[i]);
        
        maxProduct = Math.max(maxSoFar, maxProduct);
        
    }
    return maxProduct

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

An interesting challenge to solve the following problem within O(log(n)) time.

We can use the binary sort approach by checking the middle element of the array and its neighbors and following it up with either left or right side.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    return rec(nums, 0, nums.length - 1);
};

var rec = function(nums, l, r) {
    let mid = Math.round((l+r) / 2);
    if (mid == l || mid == r) {
        if (l == r) return mid; // check edge case for 1 element 
        if (nums[l] > nums[r]) return l; // check edge case for 2 elements 
        else return r;
    }
    if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid+1]) {return mid;}
    else if (nums[mid - 1] > nums[mid]) {return rec(nums, l, mid - 1);}
    else if (nums[mid + 1] > nums[mid]) {return rec(nums, mid + 1, r);}
}

Given an array arr.  You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

Solution

iterate over an array and store the number of repetitive integers in the dictionary

generate an array of integers and sort

keep adding values starting with the largest till we reach half of the array

Time Complexity: O(n*log(n)) <- due to sorting

/**
 * @param {number[]} arr
 * @return {number}
 */
var minSetSize = function(arr) {
    let freq = {}; 
    for (let i = 0; i<arr.length; i++) { // O(n)
        if (freq[arr[i]] > 0) {
            freq[arr[i]] = freq[arr[i]] + 1;
        } else {
            freq[arr[i]] = 1;
        }
    }
    
    let sorted = [];
    for(var key in freq) {
        //insert into a sorted array
        sorted.push(freq[key]);
}
    sorted.sort();
    let result = 0;
    let count = 0;
    for (let i=sorted.length-1; i>=0; i--) {
        count++;
        result = result + sorted[i];
        if (result >= arr.length / 2) {
            break;
        }
    }

    return count;
};

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Solution

Recursive function to find a path to a node and storing vector path in the array

After finding both paths compare them and return the latest element before arrays diverge.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    var pathOne = [];
    var pathTwo = [];
    
    findPath(root, pathOne, p.val);
    findPath(root, pathTwo, q.val);

    var i = 0;
    for (i = 0; i < pathOne.length && i < pathTwo.length ; i++) {
        if (pathOne[i].val != pathTwo[i].val)
            break;
    }

    return pathOne[i-1];
};

var findPath = function(root, path, nodeToFind) {
     // base case
    if (root == null) return false;
 
    // Store this node in path vector. The node will be removed if
    // not in path from root to k
    path.push(root);
 
    // See if the nodeToFind is same as root's key
    if (root.val == nodeToFind)
        return true;
 
    // Check if nodeToFind is found in left or right sub-tree
    if ( (root.left && findPath(root.left, path, nodeToFind)) ||
         (root.right && findPath(root.right, path, nodeToFind)) )
        return true;
 
    // If not present in subtree rooted with root, remove root from
    // path[] and return false
    path.pop();
    return false;
}

Problem defenition

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.Your class will be called like this: MyCalendar cal = new MyCalendar();MyCalendar.book(start, end)

Example 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
Explanation: 
The first event can be booked.  The second can't because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

• The number of calls to MyCalendar.book per test case will be at most 1000.
• In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

Solution

We can keep booking times within a sorted array, inserting every new booking in a proper place.

There are few edge cases: when we process first event, when we process an earliest event and the latest event and a general use case when we need to check if event can be inserted in the middle.

var MyCalendar = function() {
  this.log = [];
};

/** 
 * @param {number} start 
 * @param {number} end
 * @return {boolean}
 */
MyCalendar.prototype.book = function(start, end) {
    //sorted array of arrays
    if (this.log.length == 0) {
        this.log.push([start,end]);
        return true;
    }
    
    //insert all the way left
     if (end <= this.log[0][0]) {
               this.log.splice(0, 0, [start, end]);
            return true;
    }
    //insert on the right
        if (start >= this.log[this.log.length-1][1]) {
               this.log.push([start, end]);
            return true;
    }
    
    for (var i = 1; i < this.log.length; i++) {
        //insert in the middle - compare an element with a next element
        if (start >= this.log[i-1][1] && end <= this.log[i][0]){
            this.log.splice(i, 0, [start, end]);
            return true;
        } 
    }
    return false;
};

/** 
 * Your MyCalendar object will be instantiated and called as such:
 * var obj = new MyCalendar()
 * var param_1 = obj.book(start,end)
 */