Latest Questions

The supply chain manager at one of Amazon's warehouses is shipping the last container of the day. All n boxes have been loaded into the truck with their sizes represented in the array `boxes`. The truck may not have enough space to store all the boxes, so some boxes may need to be unloaded. The remaining boxes must satisfy the condition:
`max(boxes) ≤ space * min(boxes)`.

Given the array `bo xes` and an integer `space`, find the minimum number of boxes that need to be unloaded.

Example:
Given n = 4, boxes = [1, 4, 3, 2], and space = 2. This set already satisfies the condition, so the answer is 1 (minimum boxes to remove is 1).

Function Description:
Complete the function `findMaxUnloaded` in the editor below.

`findMaxUnloaded` has the following parameters:
- int boxes[n]: array representing the sizes of each box
- int space: the multiplier

Returns:
- int: the minimum number of boxes to remove from the truck

Constraints:
- 1 ≤ n ≤ 10^5
- 1 ≤ boxes[i] ≤ 5 × 10^5
- 1 ≤ space ≤ 1000

Sample Input:
n = 6
boxes = [4, 5, 3, 8, 3, 7]
space = 2

Sample Output:
2

Explanation:
Remove boxes 4 and 6 (sizes 8 and 7). Then the maximum size of the remaining boxes is 5, the minimum size is 3, and 5 ≤ 3 * 2. Alternatively, removing boxes 3 and 5 (both size 3) leaves max = 8 and min = 4, satisfying 8 ≤ 4 * 2. So, the minimum boxes to remove is 2. Show More

Determine the highest value after executing n steps on an infinite 2D grid that initially contains all zeros. The grid is indexed from (1,1) at the bottom-left corner with coordinates increasing upwards and to the right.

For each given coordinate pair (r, c), increment every cell in the rectangle from (1,1) to (r,c) inclusive by 1. After processing all coordinates, return the number of cells th at contain the maximum value in the grid.

Example:
`upRight = ["1 4", "2 3", "4 1"]`
Each string contains two space-separated integers representing the row (r) and column (c).

The process:
- Step 1: Increment cells in rectangle (1,1) to (1,4)
- Step 2: Increment cells in rectangle (1,1) to (2,3)
- Step 3: Increment cells in rectangle (1,1) to (4,1)

The overlapping region across all three rectangles is the intersection of:
- Rows: min(1, 2, 4) = 1
- Columns: min(4, 3, 1) = 1

Thus, cell (1,1) is the only cell included in all three updates. So the max value in the grid is 3, and it occurs once.

Output: `1`

Function Description:
Complete the function `countMax` in the editor below.

`countMax` has the following parameter:
- `string upRight[n]`: an array of strings where each contains two space-separated integers representing the up-right corner of a rectangle.

Return:
- `long`: the number of occurrences of the final grid's maximum value.

Constraints:
- 1 ≤ n ≤ 100
- 1 ≤ number of rows, number of columns ≤ 10^6

Sample Input:
`upRight = ["2 3", "3 7", "4 1"]`
In this case:
- Minimum of rows = min(2, 3, 4) = 2
- Minimum of columns = min(3, 7, 1) = 1
So the overlapping region is of size `2 × 1 = 2`
Output: `2` Show More

Amazon Prime Video is developing a new feature called "Segmentify." This feature applies to a video with n (even) visual frames, where each frame is represented by a binary character in the array `frames`. In this format, a "0" represents a black pixel, and a "1" represents a white pixel.

Due to factors like lighting and camera angles, some frames may need horizontal or vertical flips (changing "0"s to "1"s and vice versa) to create consistent visuals. The objective is to divide the video into subsegments so that all frames in a subsegment are visually identical (i.e., the frames in a subsegment are either all "0"s or all "1"s). Additionally, each subsegment should have an even length.

The goal is to accomplish this segmentation with two criteria in mind:
1. Minimize the number of flips required to form valid segments — let this be denoted by B.
2. Among all configurations requiring B flips, minimize the total number of subsegments.

Given the binary string `frames`, determine the minimum number of such subsegments that meet the criteria.

Note: A subsegment is a segment that can be derived from another segment by deleting some elements without changing the order of the remaining elements.

Example:
`frames = "1110011000"`
One set of optimal moves is as follows:
- Flip the first 0 to 1 → "1111011000"
- Flip the next 0 to 1 → "1111111000"
- Flip the final 0 to 1 → "1111111100"

All resulting subsegments (11111111 and 00) are of even length. So, the minimum number of subsegments is 2 with a total of 3 flips. Hence, the answer is 2.

Another example:
`frames = "110011"`
In this case, the string already consists of groups of "0"s and "1"s that have even lengths. Therefore, no flipping is necessary, and the string can be divided into 3 even-length subsegments without modification. Hence, the answer is 3.

Function Description:
Complete the function `getminSubsegments` in the editor below.

`getminSubsegments` has the following parameter:
- string `frames`: the frames of the video as a binary string.

Returns:
- int: the minimum number of subsegments.

Constraints:
- 2 ≤ n ≤ 10^5, where n is even.
- It is guaranteed that the string `frames` only consists of '0's and '1's.

Sample Input:
`100110`

Sample Output:
2

Explanation:
Flip the first 0 to 1, resulting in "110110". All segments can then be grouped into even-length parts. Show More

In this new stock prediction game launched on Amazon Games, Player 1 provides Player 2 with stock market data for n consecutive days, representing Amazon's stock prices on each day, represented by the array stockData.

The rules of the game are as follows:
1. Player 1 will tell Player 2 a specific day number i (where 1 ≤ i ≤ n).
2. Player 2 has to find the nearest day j (1 ≤ j ≤ n, j ≠ i) in t he past or future on which the stock price was lower than on the given day, i.e., stockData[j] < stockData[i].
3. If there is more than one such j, then Player 2 must choose the one with the smallest day number.
4. If no such day j exists, the answer for that query is -1.

Given q queries in the array queries, the task is to find the answer for each queries[i] in the queries and return a list of answers corresponding to each query.

Example:
n = 10
stockData = [5, 6, 8, 4, 9, 10, 8, 3, 6, 4]
queries = [6, 5, 4]

- On day 6, the stock price is 10. Both days 5 and 7 have lower prices (9 and 8 respectively). Choose day 5 because it's earlier.
- On day 5, the stock price is 9. Day 4 has a lower price of 4.
- On day 4, the stock price is 4. The only lower price is on day 8 (3).

Thus, the output is [5, 4, 8].

Function Description:
Complete the function `predictAnswer` in the editor below.

`predictAnswer` has the following parameters:
- int stockData[n]: An integer array where each element represents the stock price on day i+1 (0-based indexing).
- int queries[q]: An array where each element is a query day number (1-based indexing).

Return:
- int[q]: An array of integers where each value at index i is the answer to queries[i], as per the game rules.

Constraints:
- 1 ≤ n ≤ 10^5
- 1 ≤ stockData[i] ≤ 10^9
- 1 ≤ q ≤ 10^5
- 1 ≤ queries[j] ≤ n Show More

Amazon operates numerous warehouses, with each warehouse holding inventory[i] units of a particular product. You and your co-worker are responsible for dispatching these items to fulfill customer orders, following a specific process:

1. When dispatching from warehouse i, you begin by reducing the inventory of the i-th warehouse by dispatch1 units.
2. After your dispatch, your co-worker reduc es the inventory by dispatch2 units.
3. This process repeats until the inventory of the i-th warehouse reaches zero or becomes negative (i.e., inventory[i] ≤ 0).
4. For every warehouse that is emptied during your dispatch, you and your co-worker collectively earn 1 credit.

Your co-worker has the option to skip their turn, but they can only do this a limited number of times, defined by `skips`. Your task is to determine the best strategy to maximize the total credits that both you and your co-worker can earn together.

Example:
n = 6
inventory = [10, 6, 12, 8, 15, 1]
dispatch1 = 2
dispatch2 = 3
skips = 3

An optimal dispatch strategy is as follows:
1. Your co-worker skips 2 turns, allowing you to empty the inventory of the 1st warehouse (Inventory: 10 → 8 → 5 → 3 → 1 → -1).
2. Your co-worker doesn't skip any turns, and you empty the inventory of the 2nd warehouse (Inventory: 6 → 4 → 1 → -1).
3. Your co-worker doesn't skip any turns, and you empty the inventory of the 3rd warehouse (Inventory: 12 → 10 → 7 → 5 → 2 → 0).
4. Your co-worker skips 1 turn, and you drain the inventory of the 4th warehouse (Inventory: 8 → 6 → 3 → 1 → -1).
5. Your co-worker doesn't skip any turns, and they empty the inventory of the 5th warehouse (Inventory: 15 → 13 → 10 → 8 → 5 → 3 → 0).
6. Your co-worker doesn't skip any turns, and you empty the inventory of the 6th warehouse (Inventory: 1 → -1).

As a result, the 1st, 2nd, 3rd, 4th, and 6th warehouses were completely dispatched by you, and the two of you collectively earned 5 credits, which is the maximum possible in this scenario. Hence, the answer is 5.

Function Description:
Complete the function `getMaximumCredits` in the editor below.

`getMaximumCredits` has the following parameters:
- int inventory[n]: An array of integers denoting the inventory level of each warehouse.
- int dispatch1: An integer indicating your dispatch level per turn.
- int dispatch2: An integer indicating your co-worker's dispatch level per turn.
- int skips: An integer specifying the maximum number of times your co-worker can skip their turn.

Return:
- int: the maximum number of credits both of you can achieve collectively.

Constraints:
- 1 ≤ n ≤ 10^5
- 1 ≤ inventory[i] ≤ 10^9
- 1 ≤ dispatch1, dispatch2 ≤ 10^9
- 0 ≤ skips ≤ n Show More

In Amazon's highly efficient logistics network, minimizing operational overhead and optimizing package routing is crucial to ensure smooth deliveries across various regions. The network consists of n warehouses, numbered from 1 to n, each strategically positioned at its corresponding index. Each warehouse has a specific storage capacity, given by warehouseCapacity, where warehouseCapacity[i] repre sents the capacity of the warehouse located at position i (assuming 1-based indexing).

These warehouses are organized in a non-decreasing order of their storage capacities, meaning each warehouse's storage capacity is greater than or equal to the one before it. Each warehouse must establish a connection to a distribution hub positioned at a location greater than or equal to its own. This means that a warehouse at position i can only connect to a hub at position j where j ≥ i.

To optimize inventory routing, Amazon has placed a central high-capacity distribution hub at the last warehouse, located at position n. This hub serves as the main connection point for all warehouses if necessary. The cost of establishing a connection from warehouse at i to a hub at position j is given by warehouseCapacity[j] - warehouseCapacity[i].

Given q queries of the form (hubA, hubB), where two additional high-performance distribution hubs are deployed at warehouses hubA and hubB (1 ≤ hubA < hubB < n), the goal is to calculate the minimum total connection cost for all warehouses, considering the nearest available distribution hub at or beyond each warehouse's position.

Note:
- The problem statement assumes 1-based indexing for the warehouseCapacity array.
- Each query is independent, i.e., the changes made do not persist for subsequent queries.
- Each warehouse connects to the nearest hub at or beyond its position (either hubA, hubB, or the central hub at n) to minimize the overall connection cost.

Example:
n = 5
warehouseCapacity = [3, 6, 10, 15, 20]
additionalHubs = [[2, 4]]

In this case there is q = 1 query with two additional high-performance distribution hubs at position hubA = 2 and hubB = 4. This diagram shows the calculation of the total connection cost before additional distribution hubs are considered:

Once additional distribution hubs are installed at positions hubA = 2 and hubB = 4:
- 1st warehouse will connect to the nearest available distribution hub at position 2, cost incurred = 6 - 3 = 3
- 2nd warehouse is itself a distribution hub, so cost incurred = 0
- 3rd warehouse will connect to the nearest available distribution hub at position 4, cost incurred = 15 - 10 = 5
- 4th and 5th warehouses are themselves distribution hubs, so cost incurred = 0 + 0 = 0

Thus, the total connection cost = (6 - 3) + (0) + (15 - 10) + (0) + (0) = 8. Hence, return [8] as the answer.

Function Description:
Complete the function getMinConnectionCost in the editor below.

getMinConnectionCost has the following parameters:
int warehouseCapacity[n]: a non-decreasing array of integers representing the storage capacities of the warehouses
int additionalHubs[q][2]: an array where each element denotes the positions of two additional distribution hubs installed for a query

Returns:
long_int[q]: the answers for each query

Constraints:
- 3 ≤ n ≤ 1*10^5
- 1 ≤ q ≤ 1*10^5
- 3 ≤ n*q ≤ 1*10^9
- 0 ≤ warehouseCapacity[i] ≤ 10^9
- warehouseCapacity[i] ≤ warehouseCapacity[i + 1] for all 0 ≤ i < n - 1
- 1 ≤ additionalHubs[i][0] < additionalHubs[i][1] < n Show More

Given an n x m grid, where rows are numbered from 7 to n and columns from 1 to m, there are x blocked cells. Their positions are specified by the array blockedPositions[i][] where blockedPositions[i][1] represents the row and blockedPositions[i][2] represents the column position, using 1-based indexing.

Starting from the top-left cell (1, 1), the goal is to reach the bottom-right cell (n, m) wi thout visiting any blocked cells. Movement is allowed only up, down, left, or right.

The strength of a path is defined as the minimum Manhattan distance from each cell in the path to the nearest blocked cell. To calculate the strength of a specific path, an array minDist[] is created, where minDist[i] represents the minimum distance to any blocked cell for the ith cell visited. The strength of the path is given by min(minDist[]).

Among all possible paths from (1, 1) to (n, m), determine the path that maximizes strength. If multiple paths have the same maximum strength, select the one that visits the fewest cells.

Return two integers: the maximum strength achievable and the minimum number of cells visited. If it is impossible to navigate from (1, 1) to (n, m), return [-1, -1].

Note: The Manhattan distance between cells (a, b) and (c, d) is defined as abs(a-c) + abs(b-d).

Example n=4 Show More

There are 'N' coders standing in a line, where i denotes the ith position of a coder with a rating of Ri. All ratings are distinct.

You have to form a team of 3 from amongst them with the condition:
- Any three coders with positions (i, j, k) and ratings (Ri, Rj, Rk) can form a team when ("Ri < Rj < Rk" or "Ri > Rj > Rk") and (1 <= i < j < k <= N).

You have to find out how many such teams e xist (1 coder can be part of multiple teams).

Input:
N - 5
Ratings - 5 23 14

Output:
3
(5,2,1), (5,3,1), (2,3,4) Show More

A birthday party was attended by N number of kids, and each kid was given a unique ID ranging from 1 to N. As a return gift, there are T toys that must be distributed to the kids.

The host decided the best way to do this is by sitting the kids down in a circle (ordered by ascending ID), and then, starting with a random number D (between 1 and N), distribute one toy at a time to each sequentiall y numbered kid until all toys are distributed.

For example, if the host picks a random number D = 2, the gift distribution order would be: (2, 3, 4, 5, ... N-1, N, 1, 2, 3, 4, ...) until all T toys are distributed. The very last toy is damaged.

Your task is to determine which kid will receive the last (damaged) toy, so they can be informed and asked to exchange it at the shop.

Input:
- N (number of kids)
- T (number of toys)
- D (starting ID where distribution begins)

Output:
Print the ID of the last kid who will receive the damaged toy.

Constraints:
- 1 ≤ N ≤ 1000
- 1 ≤ T ≤ 1000
- 1 ≤ D ≤ N

Sample Input:
5
2
1

Sample Output:
2

Explanation:
There are N=5 kids and T=2 toys. Distribution starts at kid ID 1 (D=1). The distribution follows this pattern:
- Kid 1 receives the first toy.
- Kid 2 receives the second (and last) toy.

Thus, we must inform Kid 2 about the damaged toy, so we print `2` on a new line. Show More

Given a matrix of size m * n, where m denotes the number of rows (starting with index 0) and n denotes the number of columns (starting with index 0), the matrix will hold distinct integers as elements.

We need to find the distinct number of positional elements that are either the minimum or maximum in their corresponding row or column. If any row or any column has multiple minimum or maximum el ements, return -1.

Example:

Matrix of size 3 * 3:
1 3 5
8 2 7
4 9 6

The expected output is 7.

In this example, we identified the output as 7 based on the following:

- 1: Minimum in both its row and column.
- 4: Maximum in its row.
- 2: Minimum in both its row and column.
- 9: Maximum in both its row and column.
- 8: Maximum in both its row and column.
- 7: Maximum in its column.
- 6: Minimum in its row.

Thus, the total number of distinct elements that are either the minimum or maximum in their respective row or column is 7.

Input:
- m: Integer representing the number of rows.
- n: Integer representing the number of columns.
- matrix: m x n matrix of integers.

Output:
- r: Integer representing the total number of distinct elements which are either the minimum or maximum in their corresponding row or column.

Constraints:
- 0 < m, n < 100
- Elements in the matrix are positive integers. Show More