All Problems
8 problems1
Rotate Image
Given a square `n x n` matrix of integers `matrix`, rotate it by 90 degrees *clockwise*.
You must rotate the matrix *in-place*. Do not allocate another 2D matrix and do the rotation.
**Example 1:**
```java
Input: matrix = [
[1,2],
[3,4]
]
Output: [
[3,1],
[4,2]
]
```
**Example 2:**
```java
Input: matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
Output: [
[7,4,1],
[8,5,2],
[9,6,3]
]
```
**Constraints:**
* `n == matrix.length == matrix[i].length`
* `1 <= n <= 20`
* `-1000 <= matrix[i][j] <= 1000`
<br>
<br>
<details class="hint-accordion">
<summary>Recommended Time & Space Complexity</summary>
<p>
You should aim for a solution with <code>O(n^2)</code> time and <code>O(1)</code> space, where <code>n</code> is the length of the side of the given square matrix.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 1</summary>
<p>
A brute force approach would use <code>O(n^2)</code> extra space to solve the problem. Can you think of a way to avoid using extra space? Maybe you should consider observing the positions of the elements before rotating and after rotating of the matrix.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 2</summary>
<p>
We can rotate the matrix in two steps. First, we reverse the matrix vertically, meaning the first row becomes the last, the second row becomes the second last, and so on. Next, we transpose the reversed matrix, meaning rows become columns and columns become rows. How would you transpose the matrix?
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 3</summary>
<p>
Since the given matrix is a square matrix, we only need to iterate over the upper triangular part, meaning the right upper portion of the main diagonal. In this way, we can transpose a matrix.
</p>
</details>
Medium
Not Attempted
Video
2
Spiral Matrix
Given an `m x n` matrix of integers `matrix`, return a list of all elements within the matrix in *spiral order*.
**Example 1:**
```java
Input: matrix = [[1,2],[3,4]]
Output: [1,2,4,3]
```
**Example 2:**
```java
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
```
**Example 3:**
```java
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:**
* `1 <= matrix.length, matrix[i].length <= 10`
* `-100 <= matrix[i][j] <= 100`
<br>
<br>
<details class="hint-accordion">
<summary>Recommended Time & Space Complexity</summary>
<p>
You should aim for a solution with <code>O(m*n)</code> time and <code>O(1)</code> extra space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the given matrix.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 1</summary>
<p>
Try to simulate the process as described in the problem. Think in terms of matrix layers, starting from the outermost boundaries and moving inward. Can you determine an efficient way to implement this?
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 2</summary>
<p>
Each boundary consists of four parts: the top row, right column, bottom row, and left column, which follow the spiral order and act as four pointers. For each layer, the top pointer increments by one, the right pointer decrements by one, the left pointer increments by one, and the bottom pointer decrements by one.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 3</summary>
<p>
At each layer, four loops traverse the matrix: one moves left to right along the top row, another moves top to bottom along the right column, the next moves right to left along the bottom row, and the last moves bottom to top along the left column. This process generates the spiral order.
</p>
</details>
Medium
Not Attempted
Video
3
Set Matrix Zeroes
Given an `m x n` matrix of integers `matrix`, if an element is `0`, set its entire row and column to `0`'s.
You must update the matrix *in-place*.
**Follow up:** Could you solve it using `O(1)` space?
**Example 1:**
```java
Input: matrix = [
[0,1],
[1,0]
]
Output: [
[0,0],
[0,0]
]
```
**Example 2:**
```java
Input: matrix = [
[1,2,3],
[4,0,5],
[6,7,8]
]
Output: [
[1,0,3],
[0,0,0],
[6,0,8]
]
```
**Constraints:**
* `1 <= matrix.length, matrix[0].length <= 100`
* `-2^31 <= matrix[i][j] <= (2^31) - 1`
<br>
<br>
<details class="hint-accordion">
<summary>Recommended Time & Space Complexity</summary>
<p>
You should aim for a solution with <code>O(m*n)</code> time and <code>O(1)</code> space, where <code>m</code> is the number of rows and <code>n</code> is the number of columns in the given matrix.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 1</summary>
<p>
A brute force approach would iterate through the given matrix and update the corresponding row and column in a new matrix on the fly. This would result in an <code>O((m*n)*(m+n))</code> time and <code>O(m*n)</code> space solution. Can you think of a better way? Maybe you should consider using a single variable for a row and a single variable for a column instead of updating entire row and column.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 2</summary>
<p>
A better approach is to use <code>O(m+n)</code> boolean arrays. We iterate through the matrix, and when encountering a zero, we mark the respective row and column as <code>true</code>. In the second iteration, we set a cell to <code>0</code> if its corresponding row or column is marked <code>true</code>. Can you think of a way to optimize the space further?
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 3</summary>
<p>
We can use the topmost row and leftmost column of the matrix as boolean arrays by marking <code>0</code> instead of <code>true</code>. However, since they overlap at one cell, we use a single variable to track the top row separately. We then iterate through the matrix and mark zeros accordingly.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 4</summary>
<p>
In the second iteration, we update all cells that are not part of the top row or left column accordingly. After making the necessary changes, we check the top-leftmost cell and update the corresponding column. Finally, we check the extra variable and update the top row accordingly.
</p>
</details>
Medium
Not Attempted
Video
4
Non-Cyclical Number
A **non-cyclical number** is an integer defined by the following algorithm:
* Given a positive integer, replace it with the sum of the squares of its digits.
* Repeat the above step until the number equals `1`, or it **loops infinitely in a cycle** which does not include `1`.
* If it stops at `1`, then the number is a **non-cyclical number**.
Given a positive integer `n`, return `true` if it is a **non-cyclical number**, otherwise return `false`.
**Example 1:**
```java
Input: n = 100
Output: true
```
Explanation: 1^2 + 0^2 + 0^2 = 1
**Example 2:**
```java
Input: n = 101
Output: false
```
Explanation:
1^2 + 0^2 + 1^2 = 2
2^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4 (This number has already been seen)
**Constraints:**
* `1 <= n <= 1000`
<br>
<br>
<details class="hint-accordion">
<summary>Recommended Time & Space Complexity</summary>
<p>
You should aim for a solution as good or better than <code>O(logn)</code> time and <code>O(logn)</code> space, where <code>n</code> is the given integer.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 1</summary>
<p>
Create a helper function that returns the sum of the squares of a number's digits. Then, simulate the given process. If we reach <code>1</code>, return <code>true</code>. However, we may get stuck in a cycle if a number is processed more than once. What data structure can be used to detect if a number has already been processed?
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 2</summary>
<p>
We can use a hash set to detect if a number has already been processed. At each step, we update <code>n</code> with the return value of the helper function. If the result is <code>1</code>, we return <code>true</code>. If <code>n</code> is already in the set, we return <code>false</code>. Otherwise, we add <code>n</code> to the hash set and continue.
</p>
</details>
Easy
Not Attempted
Video
5
Plus One
You are given an integer array `digits`, where each `digits[i]` is the `ith` digit of a large integer. It is ordered from most significant to least significant digit, and it will not contain any leading zero.
Return the digits of the given integer after incrementing it by one.
**Example 1:**
```java
Input: digits = [1,2,3,4]
Output: [1,2,3,5]
```
Explanation `1234` + `1` = `1235`.
**Example 2:**
```java
Input: digits = [9,9,9]
Output: [1,0,0,0]
```
**Constraints:**
* `1 <= digits.length <= 100`
* `0 <= digits[i] <= 9`
<br>
<br>
<details class="hint-accordion">
<summary>Recommended Time & Space Complexity</summary>
<p>
You should aim for a solution with <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 1</summary>
<p>
There are two cases when adding <code>1</code> to a number. If the rightmost digit is less than <code>9</code>, we simply increment it. Otherwise, we set it to <code>0</code> and apply the same process to the preceding digit.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 2</summary>
<p>
We iterate through the given <code>digits</code> from right to left using index <code>i</code>. If the current digit is less than <code>9</code>, we increment it and return the array. Otherwise, we set the digit to <code>0</code> and continue. If the loop completes without returning, we insert <code>1</code> at the beginning of the array and return it.
</p>
</details>
Easy
Not Attempted
Video
6
Pow(x, n)
`Pow(x, n)` is a mathematical function to calculate the value of `x` raised to the power of `n` (i.e., `x^n`).
Given a floating-point value `x` and an integer value `n`, implement the `myPow(x, n)` function, which calculates `x` raised to the power `n`.
You may **not** use any built-in library functions.
**Example 1:**
```java
Input: x = 2.00000, n = 5
Output: 32.00000
```
**Example 2:**
```java
Input: x = 1.10000, n = 10
Output: 2.59374
```
**Example 3:**
```java
Input: x = 2.00000, n = -3
Output: 0.12500
```
**Constraints:**
* `-100.0 < x < 100.0`
* `-1000 <= n <= 1000`
* `n` is an integer.
* If `x = 0`, then `n` will be positive.
<br>
<br>
<details class="hint-accordion">
<summary>Recommended Time & Space Complexity</summary>
<p>
You should aim for a solution as good or better than <code>O(logn)</code> time and <code>O(logn)</code> space, where <code>n</code> is the given integer.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 1</summary>
<p>
A brute force approach would be to iterate linearly up to <code>n</code>, multiplying by <code>x</code> each time to find <code>(x^n)</code>. If <code>n</code> is negative, return <code>(1 / (x^n))</code>; otherwise, return <code>(x^n)</code>. Can you think of a better way? Maybe a recursive approach would be more efficient.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 2</summary>
<p>
For example, to calculate <code>2^6</code>, instead of multiplying <code>2</code> six times, we compute <code>2^3</code> and square the result. The same logic applies recursively to find <code>2^3</code> and further break down the multiplication. What should be the base case for this recursion? Maybe you should consider the term that cannot be further broken down.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 3</summary>
<p>
In <code>(x^n)</code>, if <code>x</code> is <code>0</code>, we return <code>0</code>. If <code>n</code> is <code>0</code>, we return <code>1</code>, as any number raised to the power of <code>0</code> is <code>1</code>. Otherwise, we compute <code>(x^(n/2))</code> recursively and square the result. If <code>n</code> is odd, we multiply the final result by <code>x</code>. What should be the logic if <code>n</code> is negative?
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 4</summary>
<p>
We start the recursion with the absolute value of <code>n</code>. After computing the result as <code>res</code>, we return <code>res</code> if <code>n</code> is non-negative; otherwise, we return <code>(1 / res)</code>.
</p>
</details>
Medium
Not Attempted
Video
7
Multiply Strings
You are given two strings `num1` and `num2` that represent non-negative integers.
Return the product of `num1` and `num2` in the form of a string.
Assume that neither `num1` nor `num2` contain any leading zero, unless they are the number `0` itself.
**Note**: You can not use any built-in library to convert the inputs directly into integers.
**Example 1:**
```java
Input: num1 = "3", num2 = "4"
Output: "12"
```
**Example 2:**
```java
Input: num1 = "111", num2 = "222"
Output: "24642"
```
**Constraints:**
* `1 <= num1.length, num2.length <= 200`
* `num1` and `num2` consist of digits only.
<br>
<br>
<details class="hint-accordion">
<summary>Recommended Time & Space Complexity</summary>
<p>
You should aim for a solution with <code>O(m*n)</code> time and <code>O(m+n)</code> space, where <code>m</code> is the length of the string <code>num1</code> and <code>n</code> is the length of the string <code>num2</code>.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 1</summary>
<p>
Implement a helper function that takes two number strings and returns their sum. Ensure that the length of <code>num1</code> is greater than <code>num2</code>, swapping them if necessary. Can you think of a way to multiply the strings? Maybe you should first consider basic multiplication, where <code>num1</code> is multiplied by each digit of <code>num2</code>.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 2</summary>
<p>
When multiplying <code>num1</code> with each digit of <code>num2</code>, we iterate through <code>num2</code> in reverse order. Based on the digit's position, we pad zeros to the multiplication result accordingly—no padding for the last digit, one zero for the second last, and so on. What should be the next step after each multiplication? Maybe you should implement a helper function to handle this.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 3</summary>
<p>
We implement a helper function that takes <code>num1</code>, a digit, and a variable <code>zeroes</code>, returning the multiplication result with <code>zeroes</code> padded at the end. A global string <code>res</code> stores the final result.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 4</summary>
<p>
In the main function, we iterate through <code>num2</code> in reverse order, calling the helper function to multiply <code>num1</code> with the current digit and append the appropriate number of padding zeros. We then call another helper function that takes this multiplication result and the global result string <code>res</code>, adds them, and updates <code>res</code>.
</p>
</details>
Medium
Not Attempted
Video
8
Detect Squares
You are given a stream of points consisting of x-y coordinates on a 2-D plane. Points can be added and queried as follows:
* **Add** - new points can be added to the stream into a data structure. Duplicate points are allowed and should be treated as separate points.
* **Query** - Given a single query point, **count** the number of ways to choose three additional points from the data structure such that the three points and the query point form a **square**. The square must have all sides parallel to the x-axis and y-axis, i.e. no diagonal squares are allowed. Recall that a **square** must have four equal sides.
Implement the `CountSquares` class:
* `CountSquares()` Initializes the object.
* `void add(int[] point)` Adds a new point `point = [x, y]`.
* `int count(int[] point)` Counts the number of ways to form valid **squares** with point `point = [x, y]` as described above.
**Example 1:**
```java
Input:
["CountSquares", "add", [[1, 1]], "add", [[2, 2]], "add", [[1, 2]], "count", [[2, 1]], "count", [[3, 3]], "add", [[2, 2]], "count", [[2, 1]]]
Output:
[null, null, null, null, 1, 0, null, 2]
Explanation:
CountSquares countSquares = new CountSquares();
countSquares.add([1, 1]);
countSquares.add([2, 2]);
countSquares.add([1, 2]);
countSquares.count([2, 1]); // return 1.
countSquares.count([3, 3]); // return 0.
countSquares.add([2, 2]); // Duplicate points are allowed.
countSquares.count([2, 1]); // return 2.
```
**Constraints:**
* `point.length == 2`
* `0 <= x, y <= 1000`
<br>
<br>
<details class="hint-accordion">
<summary>Recommended Time & Space Complexity</summary>
<p>
You should aim for a solution with <code>O(1)</code> time for each <code>add()</code> call, <code>O(n)</code> time for each <code>count()</code> call, and <code>O(n)</code> space, where <code>n</code> is the total number of points.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 1</summary>
<p>
Initially, we can store the points in a global list for the <code>add()</code> call. For the <code>count()</code> call, a brute force approach would use three nested loops to check other points except for the query point, resulting in an <code>O(n^3)</code> time solution. Can you think of a better way? Maybe you should consider the observation that can be drawn from the diagonal of a square.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 2</summary>
<p>
In a square's diagonal, the absolute difference between the x-coordinates is equal to the absolute difference between the y-coordinates of the two endpoints, and neither difference can be zero. Using these two points, we can determine the other diagonal endpoints.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 3</summary>
<p>
We store points in a hash map instead of a list for <code>O(1)</code> lookups, treating duplicate points as one while tracking their frequencies. For the <code>count()</code> function, we iterate through points that, along with the query point, can form a diagonal. Let the query point be <code>(qx, qy)</code> and the other point be <code>(x, y)</code>, ensuring they form a diagonal. What could be the other two points? Maybe you should consider the points forming a right-to-left diagonal, treating <code>(qx, qy)</code> as the top-right corner.
</p>
</details>
<br>
<details class="hint-accordion">
<summary>Hint 4</summary>
<p>
The other two points are point1 <code>(x, qy)</code> and point2 <code>(qx, y)</code>. For counting, we simply add <code>count of point1 * count of point2</code> to the result <code>res</code>.
</p>
</details>
Medium
Not Attempted
Video