Solving Algorithmic Problems

Description   Solution: Enumeration Use enumeration to generate all strings of length  n , level by level from length  1  to length  n . For each round, Keep track of the strings with length  i - 1 . Go through every string with length  i - 1  and generate up to two new strings appending either  0  or  1 . Note: We can only append  0  if the last character of the string is not  0 , since there can't be two consecutive  0s . Time Complexity:  O(n * 2^n) Space Complexity:  O(2^n) var validStrings = function ( n ) { let prev = [ "0" , "1" ]; for ( let i = 2 ; i <= n; i++) { let curr = []; for ( let prevStr of prev) { if (prevStr[prevStr.length - 1 ] !== '0' ) { curr.push(prevStr + '0' ); } curr.push(prevStr + '1' ); } prev = curr; } return prev; };

Description   Solution: Counting & Enumeration Count the occurances of each value in the grid, inside the Y and outside the Y. Enumerate through all combinations of the values inside the Y and outside the Y. For a combination of values  (i, j) , calculate the number of operations to change all values inside the Y to  i , and all values outside the Y to  j . Record and return the minimum operations out of all combinations. How to check if  (row, col)  is inside the Y: Separate the checks into three segments, the left part ( \ ), the right part ( / ), and the middle part ( | ). The left part ( \ ):  row <= floor(n / 2) and row === col The right part ( / ):  row <= floor(n / 2) and row + col === n - 1 The middle part ( | ):  row >= floor(n / 2) and col === floor(n / 2) Time Complexity:  O(n^2) Space Complexity:  O(1) var minimumOperationsToWriteY = function ( grid ) { let countY = Array ( 3 ).fill( 0 ); let countOut...

Description   Solution: Enumeration w/ Bitmasks Enumerate every combination of selected columns using bitmasks ( 1  to  2^n ). For each combination, count the number of rows where every  matrix[row][col] = 1  is covered by the current selected columns. Small optimization: We don't need to consider cells with value of  0 , so for each row, we can store the columns where  matrix[row][col] = 1 . This way, we don't have to unnecessarily go through every cell. m = number of rows ,  n = number of columns Time Complexity:  O(2^n * mn)  135ms Space Complexity:  O(mn)  44.8MB var maximumRows = function ( matrix, numSelect ) { let m = matrix.length, n = matrix[ 0 ].length, ones = Array (m).fill( 0 ).map( () => []); for ( let i = 0 ; i < m; i++) { for ( let j = 0 ; j < n; j++) { if (matrix[i][j] === 1 ) { ones[i].push(j); // store columns where matrix[row][col] = 1 } } } let ans = ...