CollegeStash

Author: Shiva Charan Devabhaktuni

  • Number of subsets

    For a given list of integers and integer K, find the number of non-empty subsets S such that min(S) + max(S) <= K.

    Example 1:

    nums = [2, 4, 5, 7]
k = 8
Output: 5
Explanation: [2], [4], [2, 4], [2, 4, 5], [2, 5]

    Code:

    var nums = [2, 4, 5, 7];

var findNum = function(nums, k) {
  nums.sort((a, b) => a - b);
  var count = 0;
  var low = 0;
  var high = nums.length - 1;
  while (low <= high) {
    if (nums[low] + nums[high] > k) {
      high--;
    } else {
      // Total subsets for set of n =  2^n
      count += 1 << (high - low);
      low++;
    }
  }
  return count;
}

console.log(findNum(nums, 8));
// Runtime complexity O(nlogn)
// Output: 5

    Demo

  • Shortest Distance to a Character

    class Solution {
    public int[] shortestToChar(String S, char C) {
        int n = S.length();
        int prev = Integer.MIN_VALUE/2;
        int[] store = new int[n];
        for(int i = 0; i < n; i++) {
            if(S.charAt(i) == C) {
                store[i] = 0;
                prev = i;
            }
            else 
                store[i] = i - prev; 
        }
        prev = Integer.MAX_VALUE/2;
        for(int i = n-1; i >= 0; i--) {
             if(S.charAt(i) == C)
                prev = i;
            else 
                store[i] = Math.min(store[i], prev - i); 
        }
        return store;
    }
}

  • Largest 1-Bordered Square

    class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int[][] h = new int[grid.length][grid[0].length];
        int[][] v = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    h[i][j] = 0;
                    v[i][j] = 0;
                } else {
                    h[i][j] = j > 0 ? h[i][j - 1] + 1 : 1;
                    v[i][j] = i > 0 ? v[i - 1][j] + 1 : 1;
                }
            }
        }
        int max = 0;
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                int small = Math.min(v[i][j], h[i][j]);
                while (small > max) {
                    if (v[i][j + 1 - small] >= small && h[i + 1 - small][j] >= small) {
                        max = Math.max(max, small);
                    }
                    small--;
                }
            }
        }
        return max * max;
    }
}

  • Longest Common Prefix using Binary Search (ES6)

    const arr = ["hello", "helloworld", "helloworld1"];

const allContains = (inp, start, end) => {
for(let i=0; i<inp.length; i++) {
	for(let j=start; j<=end; j++) {
		if(inp[0].charAt(j)!==inp[i].charAt(j)) {
			return false;
    	}
	}
}
return true;
};

const findSubstring = (inp) => {
let min = Number.MAX_VALUE;
  for(let i=0; i<inp.length; i++) {
  	 min = Math.min(inp[i].length, min);
  }
let low = 0, high = min-1;
let prefix = '';
 while(low<=high) {
 	let mid = low + Math.round((high-low)/2);
  	if(allContains(inp, low, mid)) {
   		prefix += inp[0].substring(low, mid+1);
  		low = mid+1;
  	} else
  	high = mid-1;
		}
return prefix;
};

console.log(findSubstring(arr));

// Output: hello
// Runtime complexity: O(m*log(n)) 
// m- length of input array or list and n is length of 
// smallest string.

    Demo

  • Verifying an Alien Dictionary (Js)

    /**
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
const isAlienSorted = function(words, order) {
  
const isInOrder = {};
  for (let i = 0; i < order.length; i++) {
    isInOrder[order.charAt(i)] = i;
  }

  search: for (let i = 0; i < words.length - 1; i++) {
    const wordBefore = words[i];
    const wordAfter = words[i + 1];
    const minWordLen = Math.min(wordBefore.length, wordAfter.length);
    for (let k = 0; k < minWordLen; k++) {
      if (wordBefore.charAt(k) !== wordAfter.charAt(k)) {
        if (isInOrder[wordBefore.charAt(k)] > isInOrder[wordAfter.charAt(k)]) {
          return false;
          }
        continue search;
      }
    }
   if (wordBefore.length > wordAfter.length) {
     return false;
     }
  }
  return true
};

console.log(isAlienSorted(['ace', 'ad'], 'abcdefghijklmnopqrstuv')); // true

    Demo

  • Filter objects (ES6)

    // There could potentially be more than 3 keys in the object below.
const items = [{
    color: 'red',
    type: 'tv',
    age: 18
  },
  {
    color: 'silver',
    type: 'phone',
    age: 20
  },
  {
    color: 'yellow',
    type: 'truck',
    age: 10
  },
  {
    color: 'blue',
    type: 'shirt',
    age: 5
  },
];

const excludes = [{
    k: 'color',
    v: 'silver'
  },
  {
    k: 'type',
    v: 'tv'
  },
  {
    k: 'color',
    v: 'red'
  }
];

// SOLUTION

const excludesMap = excludes.reduce((acc, curr) => {
  (acc[curr.k] || (acc[curr.k] = {}))[curr.v] = true;
  return acc;
}, {});

/*
color: red: true,
       green: true ... 
type: tv: true
       truck: true, ...

*/

const exclude = (items, excludes) => items.filter(item => {
  for (const [key, value] of Object.entries(item)) {
   if(excludesMap[key]?.[value])
      return false;
  }
  return true;
});

console.log(exclude(items, excludes));
/*
  [{
    age: 10,
    color: "yellow",
    type: "truck"
  }, {
    age: 5,
    color: "blue",
    type: "shirt"
  }]
*/

    Demo

  • Flatten an Array (ES6)

    To flatten an array with depth of level 1:

    const inputArray = [1, 2, 3, [4, 5]];
console.log([].concat(...inputArray));
// Output: [1, 2, 3, 4, 5]

    Demo

    To flatten an array of a specified depth:

    const input = [1, 2, 3, [4, 5, 6, [8, 9, 10]], 11, [12, 13, 14]];

const flatten = (arr, depth) =>
  depth === 0 || !Array.isArray(arr) ? arr :
  arr.reduce((acc, curr) =>
    Array.isArray(curr) ? acc.concat(flatten(curr, depth - 1)) :
    acc.concat(curr), [])

console.log(flatten(input, 3));
// Ouput: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14]

    Demo

    To flatten an array infinitely:

    const input = [1, 2, 3, [4, 5, 6, [8, 9, 10]], 11, [12, 13, 14]];

const flatten = (arr) =>
   !Array.isArray(arr) ? arr : arr.reduce((acc, curr) =>
    Array.isArray(curr) ? acc.concat(flatten(curr)) :
    acc.concat(curr), []);

console.log(flatten(input));
// Ouput: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14]

    Demo

  • Priority Queue Comparator using a HashMap

    This is similar to a MinHeap.

    import java.util.*; 
import java.lang.*;
 
public class GFG { 

    public static void main(String[] args) 
    { 
        HashMap<Integer, Integer> map 
            = new HashMap<>(); 
            map.put(10, 3);
            map.put(20, 2);
            map.put(30, 1);
      PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a,b) -> map.get(a) - map.get(b));
      pq.add(10);
      pq.add(30);
      pq.add(20);
      System.out.println(pq.poll());
      System.out.println(pq.poll());
      System.out.println(pq.poll());
    }   
}

    Output

    30
20
10

  • Rotate Matrix

    To perform in place rotation of a matrix, the matrix needs to be a square matrix (n x n i.e., n-rows and n-columns). This case is similar to a square image rotation. The Javascript (ES6) code to rotate a square matrix 90° in clockwise direction is as follows:

    const rotateMatrix = inp => {
  let n = inp.length;
  for (let layer = 0; layer < Math.floor(n / 2); layer++) {
    for (let start = layer; start < n - layer - 1; start++) {
      let temp = inp[layer][start];
      inp[layer][start] = inp[n - start - 1][layer];
      inp[n - start - 1][layer] = inp[n - layer - 1][n - start - 1];
      inp[n - layer - 1][n - start - 1] = inp[start][n - layer - 1];
      inp[start][n - layer - 1] = temp;
    }
  }
};

const matrix = [
  [3, 4, 5],
  [2, 0, 6],
  [1, 8, 7]
];
rotateMatrix(matrix);
console.log(matrix);
/*
  [
    [1, 2, 3],
    [8, 0, 4],
    [7, 6, 5]
  ]
*/

    Demo

  • CSS animation – Card Slide-In

    Using CSS @keyframes you can animate cards from left to right in the following way. This works on almost all major modern browsers.

    Demo

    Card 1

    Card 2

    <style>
.card {
  height: 100px;
  width: 250px;
  background: white;
  border-radius: 8px;
  border: 1px solid #999;
  box-shadow: 5px 5px 5px #999;
  animation: slidein 5s;
  animation-fill-mode: forwards;
  margin-right: 16px;
  transition-timing-function: cubic-bezier(0.1, 0.7, 1, 0.1);
}

@keyframes slidein {
  from {
    transform: translateX(-100%);
  }

  to {
    transform: translateX(100%);
  }
}
</style>
<div style="display:flex;">
  <div class="card">
  </div>
  <div class="card">
  </div>
  <div class="card">
  </div>
</div>