This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

On an infinite number line (x-axis), we drop given squares in the order they are given.

The `i`

-th square dropped (`positions[i] = (left, side_length)`

) is a square with the left-most point being `positions[i][0]`

and sidelength `positions[i][1]`

.

The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently landed squares. We wait for each square to stick before dropping the next.

The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they touch (either the number line or another square). Squares dropped adjacent to each other will not stick together prematurely.

Return a list `ans`

of heights. Each height `ans[i]`

represents the current highest height of any square we have dropped, after dropping squares represented by `positions[0], positions[1], ..., positions[i]`

.

**Example 1:**

Input:[[1, 2], [2, 3], [6, 1]]Output:[2, 5, 5]Explanation:After the first drop of

`positions[0] = [1, 2]: _aa _aa -------`

The maximum height of any square is 2.After the second drop of

`positions[1] = [2, 3]: __aaa __aaa __aaa _aa__ _aa__ --------------`

The maximum height of any square is 5. The larger square stays on top of the smaller square despite where its center of gravity is, because squares are infinitely sticky on their bottom edge.After the third drop of

`positions[1] = [6, 1]: __aaa __aaa __aaa _aa _aa___a --------------`

The maximum height of any square is still 5. Thus, we return an answer of`[2, 5, 5]`

.

**Example 2:**

Input:[[100, 100], [200, 100]]Output:[100, 100]Explanation:Adjacent squares don't get stuck prematurely - only their bottom edge can stick to surfaces.

**Note:**

`1 <= positions.length <= 1000`

.`1 <= positions[i][0] <= 10^8`

.`1 <= positions[i][1] <= 10^6`

.b'

\n#### Approach Framework

\n\n\n

\n#### Approach #1: Offline Propagation [Accepted]

\n\n\n

\n#### Approach #2: Brute Force with Coordinate Compression [Accepted]

\n\n\n

\n#### Approach #3: Block (Square Root) Decomposition [Accepted]

\n\n\n

\n#### Approach #4: Segment Tree with Lazy Propagation [Accepted]

\n\n\n

\n

'
\n\n

\n**Intuition**

Intuitively, there are two operations: `update`

, which updates our notion of the board (number line) after dropping a square; and `query`

, which finds the largest height in the current board on some interval. We will work on implementing these operations.

**Coordinate Compression**

In the below approaches, since there are only up to `2 * len(positions)`

critical points, namely the left and right edges of each square, we can use a technique called *coordinate compression* to map these critical points to adjacent integers, as shown in the code snippets below.

For brevity, these snippets are omitted from the remaining solutions.

\n**Python**

coords = set()\nfor left, size in positions:\n coords.add(left)\n coords.add(left + size - 1)\nindex = {x: i for i, x in enumerate(sorted(coords))}\n

**Java**

Set<Integer> coords = new HashSet();\nfor (int[] pos: positions) {\n coords.add(pos[0]);\n coords.add(pos[0] + pos[1] - 1);\n}\nList<Integer> sortedCoords = new ArrayList(coords);\nCollections.sort(sortedCoords);\n\nMap<Integer, Integer> index = new HashMap();\nint t = 0;\nfor (int coord: sortedCoords) index.put(coord, t++);\n

\n

**Intuition**

Instead of asking the question "what squares affect this query?", lets ask the question "what queries are affected by this square?"

\n**Algorithm**

Let `qans[i]`

be the maximum height of the interval specified by `positions[i]`

. At the end, we\'ll return a running max of `qans`

.

For each square `positions[i]`

, the maximum height will get higher by the size of the square we drop. Then, for any future squares that intersect the interval `[left, right)`

(where `left = positions[i][0], right = positions[i][0] + positions[i][1]`

), we\'ll update the maximum height of that interval.

**Python**

class Solution(object):\n def fallingSquares(self, positions):\n qans = [0] * len(positions)\n for i, (left, size) in enumerate(positions):\n right = left + size\n qans[i] += size\n for j in xrange(i+1, len(positions)):\n left2, size2 = positions[j]\n right2 = left2 + size2\n if left2 < right and left < right2: #intersect\n qans[j] = max(qans[j], qans[i])\n\n ans = []\n for x in qans:\n ans.append(max(ans[-1], x) if ans else x)\n return ans\n

**Java**

class Solution {\n public List<Integer> fallingSquares(int[][] positions) {\n int[] qans = new int[positions.length];\n for (int i = 0; i < positions.length; i++) {\n int left = positions[i][0];\n int size = positions[i][1];\n int right = left + size;\n qans[i] += size;\n\n for (int j = i+1; j < positions.length; j++) {\n int left2 = positions[j][0];\n int size2 = positions[j][1];\n int right2 = left2 + size2;\n if (left2 < right && left < right2) { //intersect\n qans[j] = Math.max(qans[j], qans[i]);\n }\n }\n }\n\n List<Integer> ans = new ArrayList();\n int cur = -1;\n for (int x: qans) {\n cur = Math.max(cur, x);\n ans.add(cur);\n }\n return ans;\n }\n}\n

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`positions`

. We use two for-loops, each of complexity . \n - \n
Space Complexity: , the space used by

\n`qans`

and`ans`

. \n

\n

**Intuition and Algorithm**

Let `N = len(positions)`

. After mapping the board to a board of length at most , we can brute force the answer by simulating each square\'s drop directly.

Our answer is either the current answer or the height of the square that was just dropped, and we\'ll update it appropriately.

\n**Python**

class Solution(object):\n def fallingSquares(self, positions):\n #Coordinate Compression\n #index = ...\n\n heights = [0] * len(index)\n def query(L, R):\n return max(heights[i] for i in xrange(L, R+1))\n\n def update(L, R, h):\n for i in xrange(L, R+1):\n heights[i] = max(heights[i], h)\n\n best = 0\n ans = []\n for left, size in positions:\n L = index[left]\n R = index[left + size - 1]\n h = query(L, R) + size\n update(L, R, h)\n best = max(best, h)\n ans.append(best)\n\n return ans\n

**Java**

class Solution {\n int[] heights;\n\n public int query(int L, int R) {\n int ans = 0;\n for (int i = L; i <= R; i++) {\n ans = Math.max(ans, heights[i]);\n }\n return ans;\n }\n\n public void update(int L, int R, int h) {\n for (int i = L; i <= R; i++) {\n heights[i] = Math.max(heights[i], h);\n }\n }\n\n public List<Integer> fallingSquares(int[][] positions) {\n //Coordinate Compression\n //HashMap<Integer, Integer> index = ...;\n //int t = ...;\n\n heights = new int[t];\n int best = 0;\n List<Integer> ans = new ArrayList();\n\n for (int[] pos: positions) {\n int L = index.get(pos[0]);\n int R = index.get(pos[0] + pos[1] - 1);\n int h = query(L, R) + pos[1];\n update(L, R, h);\n best = Math.max(best, h);\n ans.add(best);\n }\n return ans;\n }\n}\n

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`positions`

. We use two for-loops, each of complexity (because of coordinate compression.) \n - \n
Space Complexity: , the space used by

\n`heights`

. \n

\n

**Intuition**

Whenever we perform operations (like `update`

and `query`

) on some interval in a domain, we could segment that domain with size into blocks of size .

Then, instead of a typical brute force where we update our array `heights`

representing the board, we will also hold another array `blocks`

, where `blocks[i]`

represents the elements `heights[B*i], heights[B*i + 1], ..., heights[B*i + B-1]`

. This allows us to write to the array in operations.

**Algorithm**

Let\'s get into the details. We actually need another array, `blocks_read`

. When we update some element `i`

in block `b = i / B`

, we\'ll also update `blocks_read[b]`

. If later we want to read the entire block, we can read from here (and stuff written to the whole block in `blocks[b]`

.)

When we write to a block, we\'ll write in `blocks[b]`

. Later, when we want to read from an element `i`

in block `b = i / B`

, we\'ll read from `heights[i]`

and `blocks[b]`

.

Our process for managing `query`

and `update`

will be similar. While `left`

isn\'t a multiple of `B`

, we\'ll proceed with a brute-force-like approach, and similarly for `right`

. At the end, `[left, right+1)`

will represent a series of contiguous blocks: the interval will have length which is a multiple of `B`

, and `left`

will also be a multiple of `B`

.

**Python**

class Solution(object):\n def fallingSquares(self, positions):\n #Coordinate compression\n #index = ...\n\n W = len(index)\n B = int(W**.5)\n heights = [0] * W\n blocks = [0] * (B+2)\n blocks_read = [0] * (B+2)\n\n def query(left, right):\n ans = 0\n while left % B and left <= right:\n ans = max(ans, heights[left], blocks[left / B])\n left += 1\n while right % B != B-1 and left <= right:\n ans = max(ans, heights[right], blocks[right / B])\n right -= 1\n while left <= right:\n ans = max(ans, blocks[left / B], blocks_read[left / B])\n left += B\n return ans\n\n def update(left, right, h):\n while left % B and left <= right:\n heights[left] = max(heights[left], h)\n blocks_read[left / B] = max(blocks_read[left / B], h)\n left += 1\n while right % B != B-1 and left <= right:\n heights[right] = max(heights[right], h)\n blocks_read[right / B] = max(blocks_read[right / B], h)\n right -= 1\n while left <= right:\n blocks[left / B] = max(blocks[left / B], h)\n left += B\n\n best = 0\n ans = []\n for left, size in positions:\n L = index[left]\n R = index[left + size - 1]\n h = query(L, R) + size\n update(L, R, h)\n best = max(best, h)\n ans.append(best)\n\n return ans\n

**Java**

class Solution {\n int[] heights;\n int[] blocks;\n int[] blocks_read;\n int B;\n\n public int query(int left, int right) {\n int ans = 0;\n while (left % B > 0 && left <= right) {\n ans = Math.max(ans, heights[left]);\n ans = Math.max(ans, blocks[left / B]);\n left++;\n }\n while (right % B != B - 1 && left <= right) {\n ans = Math.max(ans, heights[right]);\n ans = Math.max(ans, blocks[right / B]);\n right--;\n }\n while (left <= right) {\n ans = Math.max(ans, blocks[left / B]);\n ans = Math.max(ans, blocks_read[left / B]);\n left += B;\n }\n return ans;\n }\n\n public void update(int left, int right, int h) {\n while (left % B > 0 && left <= right) {\n heights[left] = Math.max(heights[left], h);\n blocks_read[left / B] = Math.max(blocks_read[left / B], h);\n left++;\n }\n while (right % B != B - 1 && left <= right) {\n heights[right] = Math.max(heights[right], h);\n blocks_read[right / B] = Math.max(blocks_read[right / B], h);\n right--;\n }\n while (left <= right) {\n blocks[left / B] = Math.max(blocks[left / B], h);\n left += B;\n }\n }\n\n public List<Integer> fallingSquares(int[][] positions) {\n //Coordinate Compression\n //HashMap<Integer, Integer> index = ...;\n //int t = ...;\n\n heights = new int[t];\n B = (int) Math.sqrt(t);\n blocks = new int[B+2];\n blocks_read = new int[B+2];\n\n int best = 0;\n List<Integer> ans = new ArrayList();\n\n for (int[] pos: positions) {\n int L = index.get(pos[0]);\n int R = index.get(pos[0] + pos[1] - 1);\n int h = query(L, R) + pos[1];\n update(L, R, h);\n best = Math.max(best, h);\n ans.add(best);\n }\n return ans;\n }\n}\n

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`positions`

. Each`query`

and`update`

has complexity . \n - \n
Space Complexity: , the space used by

\n`heights`

. \n

\n

**Intuition**

If we were familiar with the idea of a segment tree (which supports queries and updates on intervals), we can immediately crack the problem.

\n**Algorithm**

Segment trees work by breaking intervals into a disjoint sum of component intervals, whose number is at most `log(width)`

. The motivation is that when we change an element, we only need to change `log(width)`

many intervals that aggregate on an interval containing that element.

When we want to update an interval all at once, we need to use *lazy propagation* to ensure good run-time complexity. This topic is covered in more depth here.

With such an implementation in hand, the problem falls out immediately.

\n**Python**

class SegmentTree(object):\n def __init__(self, N, update_fn, query_fn):\n self.N = N\n self.H = 1\n while 1 << self.H < N:\n self.H += 1\n\n self.update_fn = update_fn\n self.query_fn = query_fn\n self.tree = [0] * (2 * N)\n self.lazy = [0] * N\n\n def _apply(self, x, val):\n self.tree[x] = self.update_fn(self.tree[x], val)\n if x < self.N:\n self.lazy[x] = self.update_fn(self.lazy[x], val)\n\n def _pull(self, x):\n while x > 1:\n x /= 2\n self.tree[x] = self.query_fn(self.tree[x*2], self.tree[x*2 + 1])\n self.tree[x] = self.update_fn(self.tree[x], self.lazy[x])\n\n def _push(self, x):\n for h in xrange(self.H, 0, -1):\n y = x >> h\n if self.lazy[y]:\n self._apply(y * 2, self.lazy[y])\n self._apply(y * 2+ 1, self.lazy[y])\n self.lazy[y] = 0\n\n def update(self, L, R, h):\n L += self.N\n R += self.N\n L0, R0 = L, R\n while L <= R:\n if L & 1:\n self._apply(L, h)\n L += 1\n if R & 1 == 0:\n self._apply(R, h)\n R -= 1\n L /= 2; R /= 2\n self._pull(L0)\n self._pull(R0)\n\n def query(self, L, R):\n L += self.N\n R += self.N\n self._push(L); self._push(R)\n ans = 0\n while L <= R:\n if L & 1:\n ans = self.query_fn(ans, self.tree[L])\n L += 1\n if R & 1 == 0:\n ans = self.query_fn(ans, self.tree[R])\n R -= 1\n L /= 2; R /= 2\n return ans\n\nclass Solution(object):\n def fallingSquares(self, positions):\n #Coordinate compression\n #index = ...\n\n tree = SegmentTree(len(index), max, max)\n best = 0\n ans = []\n for left, size in positions:\n L, R = index[left], index[left + size - 1]\n h = tree.query(L, R) + size\n tree.update(L, R, h)\n best = max(best, h)\n ans.append(best)\n\n return ans\n

**Java**

class Solution {\n public List<Integer> fallingSquares(int[][] positions) {\n //Coordinate Compression\n //HashMap<Integer, Integer> index = ...;\n\n SegmentTree tree = new SegmentTree(sortedCoords.size());\n int best = 0;\n List<Integer> ans = new ArrayList();\n\n for (int[] pos: positions) {\n int L = index.get(pos[0]);\n int R = index.get(pos[0] + pos[1] - 1);\n int h = tree.query(L, R) + pos[1];\n tree.update(L, R, h);\n best = Math.max(best, h);\n ans.add(best);\n }\n return ans;\n }\n}\n\nclass SegmentTree {\n int N, H;\n int[] tree, lazy;\n\n SegmentTree(int N) {\n this.N = N;\n H = 1;\n while ((1 << H) < N) H++;\n tree = new int[2 * N];\n lazy = new int[N];\n }\n\n private void apply(int x, int val) {\n tree[x] = Math.max(tree[x], val);\n if (x < N) lazy[x] = Math.max(lazy[x], val);\n }\n\n private void pull(int x) {\n while (x > 1) {\n x >>= 1;\n tree[x] = Math.max(tree[x * 2], tree[x * 2 + 1]);\n tree[x] = Math.max(tree[x], lazy[x]);\n }\n }\n\n private void push(int x) {\n for (int h = H; h > 0; h--) {\n int y = x >> h;\n if (lazy[y] > 0) {\n apply(y * 2, lazy[y]);\n apply(y * 2 + 1, lazy[y]);\n lazy[y] = 0;\n }\n }\n }\n\n public void update(int L, int R, int h) {\n L += N; R += N;\n int L0 = L, R0 = R, ans = 0;\n while (L <= R) {\n if ((L & 1) == 1) apply(L++, h);\n if ((R & 1) == 0) apply(R--, h);\n L >>= 1; R >>= 1;\n }\n pull(L0); pull(R0);\n }\n\n public int query(int L, int R) {\n L += N; R += N;\n int ans = 0;\n push(L); push(R);\n while (L <= R) {\n if ((L & 1) == 1) ans = Math.max(ans, tree[L++]);\n if ((R & 1) == 0) ans = Math.max(ans, tree[R--]);\n L >>= 1; R >>= 1;\n }\n return ans;\n }\n}\n

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`positions`

. This is the run-time complexity of using a segment tree. \n - \n
Space Complexity: , the space used by our tree.

\n \n

\n

Analysis written by: @awice.

\n