# Posts tagged as “medium”

Alex and Lee continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first.  Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.


Constraints:

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 10 ^ 4

## Solution: Recursion + Memoization

def solve(s, m) = max diff score between two players starting from s for the given M.

cache[s][M] = max{sum(piles[s:s+x]) – solve(s+x, max(x, M)}, 1 <= x <= 2*M, s + x <= n

Time complexity: O(n^3)
Space complexity: O(n^2)

## C++

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn’t exist in the grid.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9


Example 2:

Input: grid = [[1,1,0,0]]
Output: 1


Constraints:

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] is 0 or 1

## Solution: DP

Compute the sums of all rectangles that has left-top corner at (0, 0) in O(m*n) time.
For each square and check whether its borders are all ones in O(1) time.

Time complexity: O(m*n*min(m,n))
Space complexity: O(m*n)

## C++

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].

We may make the following moves:

• 'U' moves our position up one row, if the square exists;
• 'D' moves our position down one row, if the square exists;
• 'L' moves our position left one column, if the square exists;
• 'R' moves our position right one column, if the square exists;
• '!' adds the character board[r][c] at our current position (r, c) to the answer.

Return a sequence of moves that makes our answer equal to target in the minimum number of moves.  You may return any path that does so.

Example 1:

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"


Example 2:

Input: target = "code"
Output: "RR!DDRR!UUL!R!"


Constraints:

• 1 <= target.length <= 100
• target consists only of English lowercase letters.

## Solution: Manhattan walk

Compute the coordinates of each char, walk from (x1, y1) to (x2, y2) in Manhattan way.
Be aware of the last row, we can only walk on ‘z’, so go left and up first if needed.

Time complexity: O(26*26 + n)
Space complexity: O(26*26)

## C++

Suppose you are given the following code:

class ZeroEvenOdd {
public ZeroEvenOdd(int n) { ... }      // constructor
public void zero(printNumber) { ... }  // only output 0's
public void even(printNumber) { ... }  // only output even numbers
public void odd(printNumber) { ... }   // only output odd numbers
}


The same instance of ZeroEvenOdd will be passed to three different threads:

1. Thread A will call zero() which should only output 0’s.
2. Thread B will call even() which should only ouput even numbers.
3. Thread C will call odd() which should only output odd numbers.

Each of the thread is given a printNumber method to output an integer. Modify the given program to output the series 010203040506… where the length of the series must be 2n.

Example 1:

Input: n = 2
Output: "0102"
Explanation: There are three threads being fired asynchronously. One of them calls zero(), the other calls even(), and the last one calls odd(). "0102" is the correct output.


Example 2:

Input: n = 5
Output: "0102030405"

## C++

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

• You must use only standard operations of a stack — which means only push to toppeek/pop from topsize, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

## Solution: Use two stacks

amortized cost: O(1)

## C++

Mission News Theme by Compete Themes.