The problem Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1s in the binary representation of i. Examples Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10 Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101 Constraints 0 <= n <= 10^5 Follow up: ...
The problem Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight). A set bit refers to a bit in the binary representation of a number that has a value of 1. Examples Input: n = 11 Output: 3 Explanation: The input binary string 1011 has a total of three set bits. Input: n = 128 Output: 1 Explanation: The input binary string 10000000 has a total of one set bit. Input: n = 2147483645 Output: 30 Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits. Constraints 1 <= n <= 2^31 - 1 Follow up: If this function is called many times, how would you optimize it? ...
The problem Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0s. You must do it in place. Examples Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]] Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]] Constraints m == matrix.length n == matrix[0].length 1 <= m, n <= 200 -2³¹ <= matrix[i][j] <= 2³¹ - 1 Follow up: A straightforward solution using O(m*n) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution? Brute Force Solution func setZeroes(_ matrix: inout [[Int]]) { let rows = matrix.count let cols = matrix[0].count var mark: [[Int]] = [] for r in 0 ..< rows { var row: [Int] = [] for c in 0 ..< cols { row.append(matrix[r][c]) } mark.append(row) } for r in 0 ..< rows { for c in 0 ..< cols { if matrix[r][c] == 0 { for col in 0 ..< cols { mark[r][col] = 0 } for row in 0 ..< rows { mark[row][c] = 0 } } } } for r in 0 ..< rows { for c in 0 ..< cols { matrix[r][c] = mark[r][c] } } } Explanation ...
The problem Given an m x n matrix, return all elements of the matrix in spiral order. Examples Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5] Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7] Constraints m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100 Explanation Let’s look at the example with matrix = [[1,2,3],[4,5,6],[7,8,9]] and try to figure out a way to solve this problem. ...
The problem You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Examples Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] Constraints n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 Explanation Before we jump to the solution, let’s look at how rotation was done to the matrix = [[1,2,3],[4,5,6],[7,8,9]]. ...