## Problem Statement

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

```
Function Signature (C++):
int arrangeCoins(int n)
Inputs:
n = 5
Outputs:
2
We can create rows like this:
¤
¤ ¤
¤ ¤
There are 2 full rows.
Inputs:
n = 8
Outputs:
3
We can create rows like this:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
There are 3 full rows.
```

## TL;DR Code Solution

```
int arrangeCoins(int n) {
long left = 1;
long right = n;
while (left <= right) {
long middle = (left + right) / 2;
long sum = (middle * (middle + 1)) / 2.0;
if (sum < n) {
left = middle + 1;
}
else if (sum > n) {
right = middle - 1;
}
else {
return middle;
}
}
return left - 1;
}
```

## Problem Statement

You have a grand total of n coins that you want to form into a staircase. Every k-th row must have exactly k coins to be “full”.

Given n total coins, find the total number of full staircase rows that can be formed.

You can assume that n is a non-negative integer and also fits within the range of a 32-bit signed integer.

```
Function Signature (Java):
int arrangeCoins(int n)
Inputs:
n = 5
Outputs:
2
We can create rows like this:
¤
¤ ¤
¤ ¤
There are 2 full rows.
Inputs:
n = 8
Outputs:
3
We can create rows like this:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
There are 3 full rows.
```

## TL;DR Code Solution

```
public int arrangeCoins(int n) {
int start = 0;
int end = n;
int mid = 0;
while (start <= end) {
mid = (start + end) >>> 1;
if ((0.5 * mid * mid + 0.5 * mid ) <= n) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return start - 1;
}
```

## Problem Statement

Assume that you are handing out cookies to children.

Assume also that you should give each child at most one cookie.

Each child `i`

has a greed factor `gi`

, which is the minimum size of a cookie that the child will be content with; and each cookie `j`

has a size `sj`

.

If `sj >= gi`

, we can assign the cookie `j`

to the child `i`

, and the child `i`

will be content.

Maximize the number of your content children and output the maximum number.

```
Function Signature (Java):
int findContentChildren(int[] g, int[] s)
Inputs:
g = [1,2,3]
s = [1,1]
Outputs:
1
You have 3 children and 2 cookies.
You can give one cookie to the child with greed factor 1, and he/she will be satisfied.
However, the next cookie is too small; we only have a cookie of size one, and both children left would only be satisfied with size 2 and 3 cookies.
Therefore, we can satisfy only one child.
```

## TL;DR Code Solution

```
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int gp = 0;
int sp = 0;
while (gp < g.length && sp < s.length) {
if (s[sp] >= g[gp]) {
gp++;
}
sp++;
}
return gp;
}
```

## Problem Statement

Given a binary tree, determine if it is height-balanced.

A “height-balanced” binary tree is defined as a binary tree in which the depth (height) of the two subtrees of every node are never different by more than one.

```
Function Signature (Java):
boolean isBalanced(TreeNode root)
Inputs:
o
/ \
o o
Outputs:
true
Inputs:
o
\
o
\
o
Outputs:
false
```

## TL;DR Code Solution

```
int helper(TreeNode root) {
if (root == null) {
return 0;
}
int right = helper(root.right);
if (right == Integer.MIN_VALUE) return Integer.MIN_VALUE;
int left = helper(root.left);
if (left == Integer.MIN_VALUE) return Integer.MIN_VALUE;
if (Math.abs(right - left) > 1) return Integer.MIN_VALUE;
return Math.max(right, left) + 1;
}
public boolean isBalanced(TreeNode root) {
return helper(root) != Integer.MIN_VALUE;
}
```

## Problem Statement

Given an 2D board, count the total number of battleships on it.

Battleships are represented by ‘X’s,

Board slots without a battleship are represented by ‘.’s.

Assume that you have a valid board. Every spot is empty or contains a battleship.

Battleships can only be placed vertically or horizontally.

No two battleships are adjacent. Assume there’s at least one space between each battleship.

```
Function Signature (C++):
int countBattleships(vector<vector<char>>& board)
Inputs:
X..X
...X
...X
Outputs:
2
Inputs:
...X
XXXX
...X
Invalid board - adjacent battleships.
```

## TL;DR Code Solution

```
bool isTopLeft(vector<vector<char>>& board, int i, int j) {
bool leftMost = false;
if (i == 0 || board[i-1][j] == '.') {
leftMost = true;
}
bool topMost = false;
if (j == 0 || board[i][j-1] == '.') {
topMost = true;
}
return leftMost && topMost;
}
int countBattleships(vector<vector<char>>& board) {
int result = 0;
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (board[i][j] == 'X' && isTopLeft(board, i, j)) {
result++;
}
}
}
return result;
}
```

## Problem Statement

Given an 2D board, count the total number of battleships on it. Battleships are represented by ‘X’s, and empty board slots are represented by ‘.’s. You can assume the following information:

You receive a valid board - every spot is either an empty space or contains a battleship.

Battleships are placed horizontally or vertically.

No two battleships are ‘touching’ - every battleship has a least on space of separation between them. You will have no adjacent ‘X’s that do not belong to the same battleship.

```
Function Signature (Java):
int countBattleships(char[][] board)
Inputs:
X..X.X
...X.X
...X..
Outputs:
3
Inputs:
.X..
XXXX
.X..
Invalid board - adjacent battleships.
```

## TL;DR Code Solution

```
public void dfs(char[][]board, int i, int j) {
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'X') {
return;
}
board[i][j] = 'x';
dfs(board, i+1, j);
dfs(board, i-1, j);
dfs(board, i, j+1);
dfs(board, i, j-1);
}
public int countBattleships(char[][] board) {
int result = 0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == 'X') {
result += 1;
dfs(board, i, j);
}
}
}
return result;
}
```