Math & Geometry

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](https://en.wikipedia.org/wiki/In-place_algorithm), which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Given an integer n, return the number of trailing zeroes in n!. Note that n! = n (n - 1) (n - 2) ... 3 2 1.

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Given an integer n, return true if it is a power of two. Otherwise, return false. An integer n is a power of two, if there exists an integer x such that n == 2x.

Given an m x n binary grid grid where each 1 marks the home of one friend, return the minimal total travel distance. The total travel distance is the sum of the distances between the houses of the friends and the meeting point. The distance is calculated using [Manhattan Distance](http://en.wikipedia.org/wiki/Taxicab_geometry), where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Given two [sparse matrices](https://en.wikipedia.org/wiki/Sparse_matrix) mat1 of size m x k and mat2 of size k x n, return the result of mat1 x mat2. You may assume that multiplication is always possible.

Given an integer n, return true if it is a power of three. Otherwise, return false. An integer n is a power of three, if there exists an integer x such that n == 3x.

Given an integer n, return true if it is a power of four. Otherwise, return false. An integer n is a power of four, if there exists an integer x such that n == 4x.

Assume the following rules are for the tic-tac-toe game on an n x n board between two players: 1. A move is guaranteed to be valid and is placed on an empty block. 2. Once a winning condition is reached, no more moves are allowed. 3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game. Implement the TicTacToe class: TicTacToe(int n) Initializes the object the size of the board n. int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move, and the two players alternate in making moves.

Given an m x n matrix grid where each cell is either a wall 'W', an enemy 'E' or empty '0', return the maximum enemies you can kill using one bomb. You can only place the bomb in an empty cell. The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since it is too strong to be destroyed.

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k. It is guaranteed that there will be a rectangle with a sum no larger than k.

There is an m x n binary grid matrix with all the values set 0 initially. Design an algorithm to randomly pick an index (i, j) where matrix[i][j] == 0 and flips it to 1. All the indices (i, j) where matrix[i][j] == 0 should be equally likely to be returned. Optimize your algorithm to minimize the number of calls made to the built-in random function of your language and optimize the time and space complexity. Implement the Solution class: Solution(int m, int n) Initializes the object with the size of the binary matrix m and n. int[] flip() Returns a random index [i, j] of the matrix where matrix[i][j] == 0 and flips it to 1. void reset() Resets all the values of the matrix to be 0.

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c. A province is a group of directly or indirectly connected cities and no other cities outside of the group. You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise. Return the total number of provinces.

Given an m x n binary matrix mat, return the length of the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal, or anti-diagonal.

An image smoother is a filter of the size 3 x 3 that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., the average of the nine cells in the blue smoother). If one or more of the surrounding cells of a cell is not present, we do not consider it in the average (i.e., the average of the four cells in the red smoother). Given an m x n integer matrix img representing the grayscale of an image, return the image after applying the smoother on each cell of it.

Nearly everyone has used the [Multiplication Table](https://en.wikipedia.org/wiki/Multiplicationtable). The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i j (1-indexed). Given three integers m, n, and k, return the kth smallest element in the m x n multiplication table_.

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc]. To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color. Return the modified image after performing the flood fill.

Given an m x n integer matrix grid where each entry is only 0 or 1, return the number of corner rectangles. A corner rectangle is four distinct 1's on the grid that forms an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1's used must be distinct.

Let f(x) be the number of zeroes at the end of x!. Recall that x! = 1 2 3 ... x and by convention, 0! = 1. For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has two zeroes at the end. Given an integer k, return the number of non-negative integers x have the property that f(x) = k.

There is a city composed of n x n blocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexed n x n integer matrix grid where grid[r][c] represents the height of the building located in the block at row r and column c. A city's skyline is the outer contour formed by all the building when viewing the side of the city from a distance. The skyline from each cardinal direction north, east, south, and west may be different. We are allowed to increase the height of any number of buildings by any amount (the amount can be different per building). The height of a 0\-height building can also be increased. However, increasing the height of a building should not affect the city's skyline from any cardinal direction.

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1. Return the size of the largest island in grid after applying this operation. An island is a 4-directionally connected group of 1s.

Given an n x n binary matrix image, flip the image horizontally, then invert it, and return the resulting image. To flip an image horizontally means that each row of the image is reversed. For example, flipping [1,1,0] horizontally results in [0,1,1]. To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0,1,1] results in [1,0,0].

You are given an m x n binary matrix grid. A move consists of choosing any row or column and toggling each value in that row or column (i.e., changing all 0's to 1's, and all 1's to 0's). Every row of the matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers. Return the highest possible score after making any number of moves (including zero moves).

A positive integer is magical if it is divisible by either a or b. Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a [Boustrophedon style](https://en.wikipedia.org/wiki/Boustrophedon) starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row. You start on square 1 of the board. In each move, starting from square curr, do the following: Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)]. This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board. If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next. The game ends when you reach the square n2.

Your music player contains n different songs. You want to listen to goal songs (not necessarily different) during your trip. To avoid boredom, you will create a playlist so that: Every song is played at least once. A song can only be played again only if k other songs have been played. Given n, goal, and k, return the number of possible playlists that you can create. Since the answer can be very large, return it modulo 109 + 7.

The chess knight has a unique movement, it may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). The possible movements of chess knight are shown in this diagaram: A chess knight can move as indicated in the chess diagram below: We have a chess knight and a phone pad as shown below, the knight can only stand on a numeric cell (i.e. blue cell). Given an integer n, return how many distinct phone numbers of length n we can dial. You are allowed to place the knight on any numeric cell initially and then you should perform n - 1 jumps to dial a number of length n. All jumps should be valid knight jumps. As the answer may be very large, return the answer modulo 109 + 7.

On a campus represented as a 2D grid, there are n workers and m bikes, with n <= m. Each worker and bike is a 2D coordinate on this grid. We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized. Return the minimum possible sum of Manhattan distances between each worker and their assigned bike. The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Given a matrix and a target, return the number of non-empty submatrices that sum to target. A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2. Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

Given an m x n integer matrix grid, return the maximum score of a path starting at (0, 0) and ending at (m - 1, n - 1) moving in the 4 cardinal directions. The score of a path is the minimum value in that path. For example, the score of the path 8 -> 4 -> 5 -> 9 is 4.

Given an integer n, return true if and only if it is an Armstrong number. The k\-digit number n is an Armstrong number if and only if the kth power of each digit sums to n.

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1. The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

Given a 2D grid of size m x n and an integer k. You need to shift the grid k times. In one shift operation: Element at grid[i][j] moves to grid[i][j + 1]. Element at grid[i][n - 1] moves to grid[i + 1][0]. Element at grid[m - 1][n - 1] moves to grid[0][0]. Return the 2D grid after applying shift operation k times.

Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

Given a m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for: i - k <= r <= i + k, j - k <= c <= j + k, and (r, c) is a valid position in the matrix.

Given an m x n binary matrix mat, return the number of special positions in mat. A position (i, j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

There is a strange printer with the following two special requirements: On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle. Once the printer has used a color for the above operation, the same color cannot be used again. You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid. Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false. An integer y is a power of three if there exists an integer x such that y == 3x.

You are given a positive integer primeFactors. You are asked to construct a positive integer n that satisfies the following conditions: The number of prime factors of n (not necessarily distinct) is at most primeFactors. The number of nice divisors of n is maximized. Note that a divisor of n is nice if it is divisible by every prime factor of n. For example, if n = 12, then its prime factors are [2,2,3], then 6 and 12 are nice divisors, while 3 and 4 are not. Return the number of nice divisors of n. Since that number can be too large, return it modulo 109 + 7. Note that a prime number is a natural number greater than 1 that is not a product of two smaller natural numbers.

Given two n x n binary matrices mat and target, return true if it is possible to make mat equal to target by rotating mat in 90-degree increments, or false otherwise.

A k x k magic square is a k x k grid filled with integers such that every row sum, every column sum, and both diagonal sums are all equal. The integers in the magic square do not have to be distinct. Every 1 x 1 grid is trivially a magic square. Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid.

You are given an m x n integer matrix mat and an integer target. Choose one integer from each row in the matrix such that the absolute difference between target and the sum of the chosen elements is minimized. Return the minimum absolute difference. The absolute difference between two numbers a and b is the absolute value of a - b.

You are given an m x n binary matrix grid. In one operation, you can choose any row or column and flip each value in that row or column (i.e., changing all 0's to 1's, and all 1's to 0's). Return true if it is possible to remove all 1's from grid using any number of operations or false otherwise.

You are given an m x n binary matrix grid where each cell is either 0 (empty) or 1 (occupied). You are then given stamps of size stampHeight x stampWidth. We want to fit the stamps such that they follow the given restrictions and requirements: 1. Cover all the empty cells. 2. Do not cover any of the occupied cells. 3. We can put as many stamps as we want. 4. Stamps can overlap with each other. 5. Stamps are not allowed to be rotated. 6. Stamps must stay completely inside the grid. Return true if it is possible to fit the stamps while following the given restrictions and requirements. Otherwise, return false.

An n x n matrix is valid if every row and every column contains all the integers from 1 to n (inclusive). Given an n x n integer matrix matrix, return true if the matrix is valid. Otherwise, return false.

On day 1, one person discovers a secret. You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the secret. You are also given an integer forget, which means that each person will forget the secret forget days after discovering it. A person cannot share the secret on the same day they forgot it, or on any day afterwards. Given an integer n, return the number of people who know the secret at the end of day n. Since the answer may be very large, return it modulo 109 + 7.

You are given an m x n integer matrix grid. We define an hourglass as a part of the matrix with the following form: Return the maximum sum of the elements of an hourglass. Note that an hourglass cannot be rotated and must be entirely contained within the matrix.

You are given a 0-indexed m x n integer matrix grid and an integer k. You are currently at position (0, 0) and you want to reach position (m - 1, n - 1) moving only down or right. Return the number of paths where the sum of the elements on the path is divisible by k. Since the answer may be very large, return it modulo 109 + 7.

You are given a 0-indexed m x n binary matrix grid. A 0-indexed m x n difference matrix diff is created with the following procedure: Let the number of ones in the ith row be onesRowi. Let the number of ones in the jth column be onesColj. Let the number of zeros in the ith row be zerosRowi. Let the number of zeros in the jth column be zerosColj. diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj Return the difference matrix diff.

You are given an m x n matrix grid consisting of positive integers. Perform the following operation until grid becomes empty: Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them. Add the maximum of deleted elements to the answer. Note that the number of columns decreases by one after each operation. Return the answer after performing the operations described above.

You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1). Return true if there is a path from (0, 0) to (m - 1, n - 1) that visits an equal number of 0's and 1's. Otherwise return false.

There exists an infinitely large grid. You are currently at point (1, 1), and you need to reach the point (targetX, targetY) using a finite number of steps. In one step, you can move from point (x, y) to any one of the following points: (x, y - x) (x - y, y) (2 x, y) (x, 2 y) Given two integers targetX and targetY representing the X-coordinate and Y-coordinate of your final position, return true if you can reach the point from (1, 1) using some number of steps, and false otherwise.

You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1) that has the value 1. The matrix is disconnected if there is no path from (0, 0) to (m - 1, n - 1). You can flip the value of at most one (possibly none) cell. You cannot flip the cells (0, 0) and (m - 1, n - 1). Return true if it is possible to make the matrix disconnect or false otherwise. Note that flipping a cell changes its value from 0 to 1 or from 1 to 0.

There is a knight on an n x n chessboard. In a valid configuration, the knight starts at the top-left cell of the board and visits every cell on the board exactly once. You are given an n x n integer matrix grid consisting of distinct integers from the range [0, n n - 1] where grid[row][col] indicates that the cell (row, col) is the grid[row][col]th cell that the knight visited. The moves are 0-indexed. Return true if grid represents a valid configuration of the knight's movements or false otherwise. Note that a valid knight move consists of moving two squares vertically and one square horizontally, or two squares horizontally and one square vertically. The figure below illustrates all the possible eight moves of a knight from some cell.

Given an m x n matrix, return all elements of the matrix in spiral order.

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it [in place](https://en.wikipedia.org/wiki/In-place_algorithm).

Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's. Increment the large integer by one and return the resulting array of digits.

Efficient x^n.

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

You are given a stream of points on the X-Y plane. Design an algorithm that: Adds new points from the stream into a data structure. Duplicate points are allowed and should be treated as different points. Given a query point, counts the number of ways to choose three points from the data structure such that the three points and the query point form an axis-aligned square with positive area. An axis-aligned square is a square whose edges are all the same length and are either parallel or perpendicular to the x-axis and y-axis. Implement the DetectSquares class: DetectSquares() Initializes the object with an empty data structure. void add(int[] point) Adds a new point point = [x, y] to the data structure.