XYZ CODE: Array

Showing posts with label Array. Show all posts

Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N

A P L S I I G

Y I R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3

Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4

Output: "PINALSIGYAHRPI"

Explanation:

P I N

A L S I G

Y A H R

P I

Solution

We create an 2-D array, fill it with the characters, then read line by line to get the answer.

We can re-arraynge the fills, each column has numOfRow -1 characters, go down column start at 0, go up column start at last row.

P I N

A L S I G

Y A H R

P I

class Solution {

public String convert(String s, int numRows) {

if(s == null || s.length() == 0) return "";

if(numRows == 1) {

return s;

}

char[][] arr = new char[numRows][s.length()/(numRows-1)+1];

boolean down = true;

int counter = 1;

int row = 0;

int col = 0;

for(char c : s.toCharArray()) {

arr[row][col] = c;

row += down ? 1 : -1;

if(counter == numRows - 1) {

if(down) {

row = arr.length - 1;

} else {

row = 0;

}

down = !down;

counter = 1;

col++;

} else {

counter++;

}

StringBuilder sb = new StringBuilder();

for(int i = 0; i < arr.length; i++) {

for(int j = 0; j < arr[0].length; j++) {

if(arr[i][j] != '\u0000') {

sb.append(arr[i][j]);

}

return sb.toString();

}

Time complexity: O(N), each character need to be processed once.

Space complexity: O(N), the 2-D matrix has roughly numOfRows x (N/numOfRows) with is proportional to N.

Problem

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");

trie.search("apple"); // returns true

trie.search("app"); // returns false

trie.startsWith("app"); // returns true

trie.insert("app");

trie.search("app"); // returns true

Note:

You may assume that all inputs are consist of lowercase letters a-z.

All inputs are guaranteed to be non-empty strings.

Solution

Trie data structure is a multi-node tree. While tree Node as 2 child node, trie node has 26 child node stored in an array. It has an additional boolean field marking the end of a word.

import java.util.*;

class Solution {

public static void main(String...args) {

Trie trie = new Trie();

trie.insert("apple");

System.out.println(trie.search("apple")); // returns true

System.out.println(trie.search("app")); // returns false

System.out.println(trie.startsWith("app")); // returns true

trie.insert("app");

System.out.println(trie.search("app")); // returns true

}

class Trie {

TrieNode root;

private static class TrieNode {

TrieNode[] next = new TrieNode[26];

boolean isEnd = false;

}

/** Initialize your data structure here. */

public Trie() {

root = new TrieNode();

}

/** Inserts a word into the trie. */

public void insert(String word) { //apple

insert(root, word, 0);

}

private void insert(TrieNode node, String word, int n) { //1

if(n == word.length()) {

return;

}

int p = word.charAt(n) - 'a';

TrieNode next = node.next[p];

if(next == null) {

next = new TrieNode();

node.next[p] = next;

}

if(n == word.length() - 1) {

next.isEnd = true;

}

insert(next, word, n+1);

}

/** Returns if the word is in the trie. */

public boolean search(String word) {

return search(root, word, 0);

}

private boolean search(TrieNode node, String word, int n) {

int p = word.charAt(n) - 'a';

TrieNode next = node.next[p];

if(next == null) {

return false;

} else {

if(n == word.length() - 1) {

return next.isEnd;

}

return search(next, word, n+1);

}

/** Returns if there is any word in the trie that starts with the given prefix. */

public boolean startsWith(String prefix) {

return startsWith(root, prefix, 0);

}

private boolean startsWith(TrieNode node, String word, int n) {

int p = word.charAt(n) - 'a';

TrieNode next = node.next[p];

if(next == null) {

return false;

} else {

if(n == word.length() - 1) {

return true;

}

return startsWith(next, word, n+1);

}

The time complexity is O(w) for all 3 operations, where w is the length of word. We need to process each character in the word of length w.

The space complexity is O(w) for all 3 operations.

For insert, we create w TrieNode, TrieNode has a size 26 array and a boolean field, we assume its size is constant.
For search and startsWith, the recursive call stack is w layer deep, so the space also proportional to O(w).

Longest Increasing Path in a Matrix

Problem

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums =

[

[9,9,4],

[6,6,8],

[2,1,1]

]

Output: 4

Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums =

[

[3,4,5],

[3,2,6],

[2,2,1]

]

Output: 4

Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution

We can use graph dfs traversal start at each node for find the increasing paths. Since we need to find the max length path, we need to explore all the possibilities. This is a time we think of backtracking. We need to explore all the other directions once we tested one direction. At each node, there will be 3 possible directions that have increasing number, for a m x n matrix, we could end up exploring power(3, mn) states for each node. We can cut down the computation with memorization. We remember the longest increasing path for each node, that way, each node only have to be processes once and the cost reduced to O(mn) for each node. Since there are mn nodes total, the time complexity is O(mmnn), the space complexity is O(mn) for the memorization cache.

import java.util.*;

class Solution {

int maxLen = Integer.MIN_VALUE;

int[][] nums =

{

{9,9,4},

{6,6,8},

{2,1,1}

};

int[][] memo = new int[nums.length][nums[0].length];

public static void main(String[] args) {

Solution sol = new Solution();

sol.solve();

System.out.println(sol.maxLen);

}

private void solve() {

for(int row = 0; row < nums.length; row++) {

for(int col = 0; col < nums[0].length; col++) {

memo[row][col] = dfs(row, col);

maxLen = Math.max(maxLen, memo[row][col]);

}

private int dfs(int row, int col) {

if(memo[row][col] != 0) {

return memo[row][col];

}

int[][] directions = new int[][]{

{0, 1},

{0, -1},

{1, 0},

{-1, 0}

};

int tmpMax = 1;

for(int[] direct: directions) {

int newRow = row + direct[0];

int newCol = col + direct[1];

if(newRow >= 0 && newRow < nums.length && newCol >= 0 && newCol < nums[0].length && nums[row][col] < nums[newRow][newCol]) {

int len = dfs(newRow, newCol);

memo[newRow][newCol] = len;

tmpMax = Math.max(tmpMax, 1 + len);

}

return tmpMax;

}

Valid Anagram

Problem

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"

Output: true

Example 2:

Input: s = "rat", t = "car"

Output: false

Note:

You may assume the string contains only lowercase alphabets.

Solution

We can compare the frequency of the characters.

import java.util.*;

class Solution {

public static void main(String[] args) {

String s = null, t = "";

System.out.println(solve(s, t));

}

private static boolean solve(String s, String t) {

if(s == null || t == null)

throw new IllegalArgumentException("bad input");

char[] freq = new char[26];

for(char c : s.toCharArray()) {

freq[c - 'a']++;

}

for(char c : t.toCharArray()) {

freq[c - 'a']--;

if(freq[c - 'a'] < 0)

return false;

}

for(int i : freq) {

if(i != 0)

return false;

}

return true;

}

The time complexity is O(max(L1, L2)), space complexity is O(max(L1, L2)), where L1 and L2 is the length of the two strings.

Longest Turbulent Subarray

Problem:

A subarray A[i], A[i+1], ..., A[j] of A is said to be turbulent if and only if:

For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;

OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.

Return the length of a maximum size turbulent subarray of A.

Example 1:

Input: [9,4,2,10,7,8,8,1,9]

Output: 5

Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])

Example 2:

Input: [4,8,12,16]

Output: 2

Example 3:

Input: [100]

Output: 1

Note:

1 <= A.length <= 40000

0 <= A[i] <= 10^9

Solution:

We can use a pointer mark the start position of a turbulent subarray, then move the tail of turbulent subarray one step at a time. At each step, we compare the current value with previous and next value to check if we can move the tail one step further. If we can not move the tail further, the current position is the end of a turbulent subarray and the start of the next turbulent subarray. So calculate the length of the previous turbulent subarray, then we move the starting point here to mark the beginning of the next turbulent subarray. The problem's difficulty is in the details of no changing sequence, we need to consider the special case of 1, 1, 1, 1, 1, 1, 1, 1. The solution should return 1 instead of 2.

class Solution {
public static void main(String...args) {
int[] arr = new int[]{3};
System.out.println(solve(arr));
}
private static int solve(int[] arr) {
int start = 0;
int result = 1; //2
if(arr.length == 1) return 1;
//8 8 8 8 8 8 8 8
for(int i = 1; i < arr.length; i++) { //9,4,2,10,7,8,8,1,9
if(i == arr.length - 1 || (Integer.compare(arr[i], arr[i-1]) * Integer.compare(arr[i+1], arr[i]) >= 0)) {
if((arr[i] - arr[i-1]) != 0) {
result = Math.max(result, i - start + 1);
}
start = i;
}
}
return result;
}
}

The time complexity is O(N) because we iterate the array only once, the space complexity is O(1).

Maximum Subarray

Problem:

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum.

For Example:

Given input: [-2,1,-3,4,-1,2,1,-5,4],

output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

Solution:

We can iterate the array, add the current number to the sum. If the sum is negative, we don't want to carry it to calculate the total with the next number, whenever we get a negative sum, we want to start over, because adding a negative number only makes the total smaller.

In case all the numbers are non-positive, we return the largest negative number, in another words, we don't sum up negative numbers.

class Solution {
public static void main(String...args) {
int[] arr = new int[]{-2,1,-3,4,-1,2,1,-5,4};
System.out.println(largestSum(arr));
}

public static int largestSum(int[] arr) {
int max = Integer.MIN_VALUE;
int count = 0;
for(int i = 0; i < arr.length; i++) {
count += arr[i];
if(count > 0) {
max = Math.max(max, count);
}
else {
max = Math.max(max, arr[i]);
count = 0;
}
}
return max;
}
}

The time complexity is O(N), the space complexity is O(1).

Subarrays with K Different Integers

Problem:

Subarrays with K Different Integers

Given a positive integer array and a target k, return the number of subarrays with distinct integers equal to k. The subarray elements need to be contiguous but not necessarily distinct.

For example,

given [1,2,3,1,2] and k = 2

the output is 4.

there are 4 subarrays with 2 distinct integers.

[1, 2] [2, 3] [3, 1], [1, 2]

given [1,2,3,1,2] and k = 3

the output is 5.

there are 5 subarrays with 3 distinct integers.

[1, 2, 3], [1, 2, 3, 1] [2, 3, 1] [2, 3, 1, 2] [3, 1, 2]

given [1,2,3,1,2] and k = 0

the output is 5.

given [1,2,3,1,2] and k = 10

the output is 0.

Solution:

This is a sliding window problem, quite similar to Longest Substring with At Most K Distinct Characters, here we are dealing with integer array instead of character array or string.

We put the left pointer and right pointer of the sliding window at initial position 0. Then we move the right pointer to expand the sliding window and move the left pointer to shrink the sliding window.

The right pointer is moved one step at a time, once the distinct integers in the sliding window is equal to k, we start to move the left pointer. Here we need to deal with the following situation:

1, 1, 1, 1, 1, 1, 2, 3, 4

All the subarrays with leading 1s are valid subarrays with distinct integers equal to 4. So we need 2 sliding windows that seak the begin and end of the 1s.

For the datastructure that count the distinct integers in a sliding window, we can use a HashMap to record the repeating time for each integer.

import java.util.*;
class Solution {
public static void main(String...args) {
int[] arr = new int[]{1,2,3,1,2};
int k = 2;
System.out.println(subarrays(arr, k));
k = 3;
System.out.println(subarrays(arr, k));
k = 1;
System.out.println(subarrays(arr, k));
k = 10;
System.out.println(subarrays(arr, k));
}
public static int subarrays(int[] arr, int k) {
if(k <= 1 || arr == null) throw new RuntimeException("invalid parameter");
if(k == 1)
return arr.length;
int result = 0;
SlidingWindow win1 = new SlidingWindow();
SlidingWindow win2 = new SlidingWindow();
int lp1 = 0;
int lp2 = 0;
for(int i = 0; i < arr.length; i++) {
win1.add(arr[i]);
win2.add(arr[i]);
while(win1.getNumOfUnique() > k) {
win1.remove(arr[lp1++]);
}
while(win2.getNumOfUnique() >= k) {
win2.remove(arr[lp2++]);
}
result += lp2 - lp1;
}
return result;
}

private static class SlidingWindow {
private int numOfUnique = 0;
private Map<Integer, Integer> freq = new HashMap<>();
public void add(int i) {
freq.put(i, freq.getOrDefault(i, 1));
if(freq.get(i) == 1) {
numOfUnique++;
}
}
public void remove(int i) {
int count = freq.get(i);
if(count == 1) {
numOfUnique--;
freq.remove(i);
}
}
public int getNumOfUnique() {
return numOfUnique;
}
}
}

The time complexity is O(N), the left pointers and right pointer only iterate the integer array once.

The space complexity is O(N), the HashMap could have size N.

Moving Stones Until Consecutive II

Problem:

On an infinite number line, the position of the i-th stone is given by stones[i]. Call a stone an endpoint stone if it has the smallest or largest position.

Each turn, you pick up an endpoint stone and move it to an unoccupied position so that it is no longer an endpoint stone.

In particular, if the stones are at say, stones = [1,2,5], you cannot move the endpoint stone at position 5, since moving it to any position (such as 0, or 3) will still keep that stone as an endpoint stone.

The game ends when you cannot make any more moves, ie. the stones are in consecutive positions.

When the game ends, what is the minimum and maximum number of moves that you could have made? Return the answer as an length 2 array: answer = [minimum_moves, maximum_moves]

Example 1:

Input: [7,4,9]
Output: [1,2]
Explanation:
We can move 4 -> 8 for one move to finish the game.
Or, we can move 9 -> 5, 4 -> 6 for two moves to finish the game.
Example 2:

Input: [6,5,4,3,10]
Output: [2,3]
We can move 3 -> 8 then 10 -> 7 to finish the game.
Or, we can move 3 -> 7, 4 -> 8, 5 -> 9 to finish the game.
Notice we cannot move 10 -> 2 to finish the game, because that would be an illegal move.
Example 3:

Input: [100,101,104,102,103]
Output: [0,0]

Solution:

Let's play the game for a while.

First of all, we should put the stones in the right positions, otherwise this game won't be a playable fun game.

For maximum it is just the sum of the gaps between each stone. We can move the left boundary stone next to the right boundary stone, then move right boundary stone next to the left boundary stone, so on and so forth. Each move shrinks the total length by one. But if we take the 1st stone then we cannot count the gaps between 1st and 2nd stone. Similarly if we take the last stone then we cannot count the gaps between last and 2nd last stone. Thus we need to take the maximum of these two cases.

Next let's work on the minimum number of moves. For the first move, let's pick up the stone from the side that will eliminate more empty spaces after moving, a reasonable choice. Where should the stone be put down? There are many choices which all makes sense, but those positions should be somewhere in the range with most dense stone populations. That tuition leads us to a mathematical imagination for how the end game should look like.

For minimum number of moves, the final arrangement will be of the form [a, a+1, a+2, ... a+L-1] for L stones for some 'a'. The possible values of 'a' are all the stone positions in the given input array. The reason a is at stone position is because, if it is not at stone position, we can move the range to [a+1, a+2, ... a+L], which didn't lost a stone at left boundary, but could possibly included a new stone at the right boundary. More stone in the range is a favorable situation. We can keep doing this until a is at the next stone position. The right boundary a+L-1 could be at either stone position or empty position.

For each possible 'a', check how many positions (from a to a+L-1) already have stones. We need to fill in the missing remaining positions. Thus if there are K missing positions we need K moves to fill them. Compute K for each value of 'a' and take their minimum.

To achieve the goal, we can use sliding window. The window initially contains 2 stones. The stones in the window exclude the right boundary. We expand the window one stone interval if the positions inside the window can not hold L stones, otherwise register a min move count, then shrink the window one stone interval.
When register a min move count, there are 2 conditions:

There is only one empty position in the sliding window. In that case, we have to move the right boundary stone to complete the game. We don't move the left boundary stone to complete the game, because in the next iteration, when we shrink the sliding window, that case will be covered. When we move the right boundary stone to finish the game, we need to make sure the empty position is not next to the right boundary.
There are more than one empty positions in the sliding window. In that case, we know there are at least 2 stones outside the sliding window. We can use 1 stone to fill the empty position next to the right boundary of the sliding window, so that we won't get into condition 1 in later moves.

import java.util.*;
class Solution {
public static void main(String...args) {
int[] pos = new int[]{7,4,9};
int[] ans = maxmin(pos);
System.out.println("[" + ans[0] + ", " + ans[1] + "]");
}

public static int[] maxmin(int[] pos) {
if(pos.length == 2) {
throw new RuntimeException("more than 3 stones please");
}
int[] ans = new int[2];
Arrays.sort(pos);
ans[0] = min(pos);
ans[1] = max(pos);
return ans;
}

//4 . . 7 . 9
private static int min(int[] pos) {
int l = 0; //sliding window left boundary
int r = 1; //sliding window right boundary
int min = Integer.MAX_VALUE;
int stones = 1;
int gaps = 0;
while(r < pos.length) {
if(pos[r] <= pos[l] + pos.length-1) { //expand sliding window
stones++;
r++;
} else {
gaps = pos.length - stones;
if(gaps == 1 && pos[r - 1] == pos[l] + pos.length - 1 || gaps != 1) {
min = Math.min(min, gaps);
}
l++; //shrink sliding window
stones--;
}
}
gaps = pos.length - stones;
if(gaps == 1 && pos[r - 1] == pos[l] + pos.length - 1 || gaps != 1) {
min = Math.min(min, gaps);
}
return min;
}

//4 . . 7 . 9
private static int max(int[] pos) {
int total = pos[pos.length - 1] - pos[0] + 1; //9 - 4 + 1 = 6
int space = total - pos.length;
//remove 1st interval or last interval
return Math.max(space - (pos[1] - pos[0] - 1), space - (pos[pos.length - 1] - pos[pos.length - 2] - 1));
}
}

The time complexity for sorting is O(NlogN), the space complexity is O(1).

Number of Submatrices That Sum to Target

Problem:

Given a matrix, and a target, return the number of non-empty submatrices that sum to target.

For example, given matrix
{
{0, 1},
{0, 1}
}
and target 0, the output should be 3.
Given the same matrix and target 1, the output should be 4.
Given the same matrix and target 2, the output should be 2.
Given the same matrix and target 3, the output should be 0.

Solution:
We have solved Subarray Sum Equals K before, this problem can be converted to that problem then get solved. The matrix involved in Subarray Sum Equals K is a 1D array, while we are dealing with 2D array here.

We can calculate the prefix sum of the original array, then any submatrices' sum can be calculated with from the prefix sum matrix. curr_sum = sum[r2][col] - sum[r1 - 1][col]. In 2D the prefix sum is a sum of the current value with the integers above or on the left.

prefix sum

For example:

0 0 0
0 1 0 0 1
0 1 0 0 2

Now we can write the code

import java.util.*;
class Solution {
public static void main(String...args) {
int[][] arr = new int[][]
{
{0, 1},
{0, 1}
};
int target = 0;
System.out.println(numOfsubArrays(arr, target));
target = 1;
System.out.println(numOfsubArrays(arr, target));
target = 2;
System.out.println(numOfsubArrays(arr, target));
target = 3;
System.out.println(numOfsubArrays(arr, target));
}

public static int numOfsubArrays(int[][] arr, int target) {//0
int r = arr.length; //2
int c = arr[0].length; //2
int[][] sum = new int[r+1][c+1]; //sum matrix is bigger than the orginal max
//fill the sum from index 1,1 to r,c, not filled cells remain 0.
for(int i = 1; i < r+1; i++) {
for(int j = 1; j < c+1; j++) {
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i-1][j-1];
}
}
/*
0 0 0
0 0 1
0 0 2
*/
int count = 0;
Map<Integer, Integer> vals = new HashMap<>();
for(int i = 0; i < r; i++) {
for(int j = i+1; j < r+1; j++) {
//with fixed row, 2D Subarray Sum Equals K problem converts to 1D Subarray Sum Equals K
vals.clear();
for(int k = 0; k < c+1; k++) { //k=0, so we can have val.put(0, 0)
int delta = sum[j][k] - sum[i][k];
count += vals.getOrDefault(delta - target, 0);
vals.put(delta, vals.getOrDefault(delta, 0) + 1);
}
}
}
return count;
}
}

The time complexity is O(RRC) for the 3 layered loop, the space complexity is O(RC) for the prefix sum matrix.

see also:
Subarray Sum Equals K

Subarray Sum Equals K

Problem:

Number of subarrays that Sum to Target

Given an integer array, and a target, return the number of non-empty subarrys that sum to target.

For example, Given array [1, 2, 3] and target 3:
subarray [1, 2] and [3] sum to 3, so the answer is 2.

Solution:

The brutal force solution is to iterate all the indexes, at each position, we iterate all the indexes on the right, calculate the sum and compare with the target. The time complexity is O(N^2) and the space complexity is O(1).

A common pitfall solution is to use sliding window to achieve time complexity O(N) and space complexity O(1) performance. Do you see what's wrong with the following solution?

class Solution {
public static void main(String...args) {
int[] arr = new int[]{1, 2, 3};
int target = 3;
System.out.println(numOfsubArrays(arr, target));
}

/*
1 2 3
.
*
sum = 3
count = 2
*/
public static int numOfsubArrays(int[] arr, int target) {
int left = 0;
int n = arr.length;
int count = 0;
int sum = 0;
for(int i = 0; i < arr.length; i++) {
sum += arr[i];
if(sum == target)
count++;
while(sum > target && left <= i) {
sum -= arr[left];
left++;
if(sum == target)
count++;
}
}
return count;
}
}

The code works only if all the elements in the array is positive integer. The above solution is based on the assumption that, when we include a new element in the sliding window, the sum increases, when we remove an old element from the sliding window, the sum decreases. This assumption won't hold if we have negative elements in the subarray.

Actually, if we use a Hashmap to trade space for time, there is a time complexity O(N) and space complexity O(N) solution.

The model is as follows: we iterate from left to right of the array and calculate the sum of elements we saw so far. If we saw a new sum, we put the sum as key and 1 as value to the hashmap. If we saw the same sum later, we increase the value by 1. The reason we build this model is, given any 2 sum[j] and sum[i], the subarray's sum between j and i can be calculated with sum[j] - sum[i]. If the result is equal to k, we found a match.

Now, at each position, we subtract the target from the sum, then use the result as key to look up the hashmap. If we found a match, that means, the current sum minus some previous sum equal to target, which means, the subarray between a previous index and current index sum up to target. We kept saying "some previous sum", how many? It is equal to the value in the hashmap.

import java.util.*;
class Solution {
public static void main(String...args) {
int[] arr = new int[]{3, 4, 7, 2, -3, 1, 4, 2};
int target = 7;
System.out.println(numOfsubArrays(arr, target));
}

public static int numOfsubArrays(int[] arr, int target) {
Map<Integer, Integer> sumCount = new HashMap<>();
int sum = 0;
int count = 0;
for(int i = 0; i < arr.length; i++) {
sum += arr[i];
if(sumCount.get(sum - target) != null) {
count += sumCount.get(sum - target);
}
sumCount.put(sum, sumCount.getOrDefault(sum, 1));
}
return count;
}
}

The time complexity is O(N), we need to iterate the array once, the space complexity is O(N), we need a size N hashmap to store the same sum count.

Sliding Window Maximum

Problem:

Given an integer array and an Integer k, k represents a sliding window with size k that starts at the array's left end, moves one step at a time until reaches the array's right end. Each time the sliding window moves, it brings in a new number from right and removes an old number at left. Return an array which contains the max number in the sliding window at each move.

For Example:

Given array [1,3,-1,-3,5,3,6,7], and k = 3
The output is: [3,3,5,5,6,7]
Explanation:

Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

1 <= k <= array.length

Solution:

The brutal force solution is search k elements for the max at each array index from 0 to n - k. The time complexity will be nk.

There is a time complexity O(N) solution if we redesign the problem.

We can divide the original array into k sized chunks. When the k sized sliding window slides through the array, the chunk's boundary will cut the window into 2 parts. The original problem of finding the max value in the sliding window is converted to find the max value for the left half, max value for the right half, then combine the 2 max values we can find the max value in the sliding window.

imaginary boundary cut the k sized sliding window into 2 halves

With the imaginary k sized boundary added, the rest of the work is easy. In order to find the max value for the left half of the sliding window, we only have to scan from the boundary leftward, for the max value for the right half of the sliding window, we only have to scan from the boundary rightward. We can scan these max values and store them in array left and right. Then we can iterate the original array, use the pre-scanned left and right max value arrays to find the left half and right half's max values.

import java.util.*;
public class Solution {
public static int[] maxNum(int[] arr, int k) {
int n = arr.length;
int[] result = new int[n - k + 1];
int[] left = new int[n];
int[] right = new int[n];
left[0] = arr[0];
right[n - 1] = arr[n - 1];
for(int i = 1; i < n; i++) {
//left -> right
if(i % k == 0) {
left[i] = arr[i]; //reset max at boundary
} else {
left[i] = Math.max(left[i - 1], arr[i]); //compare with left
}
//right -> left
if((n - i) % k == 0) {
right[n - i - 1] = arr[n - i - 1]; //reset max at boundary
} else {
right[n - i - 1] = Math.max(right[n - i], arr[n - i - 1]); //compare with right
}
}
for(int i = 0; i <= n - k; i++) {
result[i] = Math.max(right[i], left[i + k - 1]); //right[i] is the max value of the sliding window's left half
}
return result;
}

public static void main(String...args) {
int[] arr = new int[]{1,3,-1,-3,5,3,6,7};
for(int i : maxNum(arr, 3)) {
System.out.print(i + " ");
}
}
}

We need to iterate the array once to generate the max value array left and right, we need to iterate the array the second time to calculate the sliding window's left and half max value, then combine them to find the max value in the sliding window. The time complexity is O(N), the space complexity is O(N) because of the left and right array for max values.

Longest Substring Without Repeating Characters

Problem:

Given a string, find the length of the longest substring without repeating characters.

For Example:

Input: "xxyzxzzy"
Output: 3
Explanation: The answer is "xyz", with the length of 3.

Input: "mmmmmm"
Output: 1
Explanation: The answer is "m", with the length of 1.
Example 3:

Input: "hmmqmym"
Output: 3
Explanation: The answer is "qmy", with the length of 3.

Solution:

We can use a sliding window, find all the combinations of the end index and start index, check if substring(start, end) have duplicate character, the start and end index need two loops, check duplicate need another loop. The total cost will be O(N^3).

We can do this smarter.
The duplicate check can be done with a HashMap, which has cost of 1 instead of N.

If substring [start, end) has already been checked for duplicate, then to check duplicate for substring [start, end + 1) is to check if the character at index end is already in the substring [start, end), which is a cost 1 HashMap call.

Anther observation is: if a character has duplicate at index k in the range [i, j), the start index can advance to k + 1, skip all the duplicate check between [i, k]. The reason is, any substring start before k, will bound to find duplicate at current examine index, the only chance for no duplicate substring start at k + 1.

import java.util.*;
class FindLongestSubString {

//abbcprqmpaq
private static String getLongest(String word) {
//sliding window, advance start index and end index
Map<Character, Integer> nextPos = new HashMap<>();
int maxLength = 0;
int startIndex = 0;
for(int start = 0, end = 0; end < word.length(); end++) { //end = 10q
if(nextPos.containsKey(word.charAt(end))) {
start = Math.max(start, nextPos.get(word.charAt(end))); //7
}
if(end - start + 1 > maxLength) { //6
maxLength = end - start + 1; //6
startIndex = start; //2
}
nextPos.put(word.charAt(end), end + 1); //a10;b3;c4;p9;r6;q11;m8
}
return word.substring(startIndex, startIndex + maxLength);
}
public static void main(String...args) {
String result = getLongest("abbcprqmpaq");
System.out.println(result);
result = getLongest("abbcprqmpaqx");
System.out.println(result);
result = getLongest("abbcrqmppaqx");
System.out.println(result);
result = getLongest("abbcprqmpazx");
System.out.println(result);
result = getLongest("mznhieabbcprqmpazx");
System.out.println(result);
}
}

The time complexity is O(N), we need to iterate the word, cost for hashmap is 1. The space complexity is O(N) which is the size of the hashMap

This is a typical sliding window problem, we use a mask to hide the whole string, only reveal a window for part of the string, then study its property. The sliding window has a left and right edge, we move the left edge to mask unconcerned characters, we move the right edge to reveal more character into concern. For this particular problem, we move the right edge 1 step at a time to reveal one more character until visited the whole string. If the new character has been seen before at index k, we can safely move left edge to k+1, ignoring all the substrings before position k. It is because any substring that includes the same character at index k will have duplicate. Now the substring in the sliding window's left and right edge form a candidate for the longest substring without duplicate. To remember the last time we saw a character, we can use a HashMap, however, since the characters are limited, we can use an array for the same purpose, size 128 array for ASCII and 256 for extended ASCII.

public class Solution {
public static String longestSubString(String str) { //x
String longest = "";
int[] lastSeen = new int[256];
int i = 0, j = 0;
while(j < str.length()) { //i=2, j=5
Character c = str.charAt(j++); //x
i = Math.max(i, lastSeen[c]);
lastSeen[c] = j; //x:5, y:3, z= 4
if(longest.length() < j - i) {
longest = str.substring(i, j); //xyz
}
}
return longest;
}
public static void main(String...args) {
System.out.println(longestSubString("xxyzxzzy"));
}
}

The time complexity is O(N), we only go through the array once. The space complexity is O(N), the longest substring can only be as long as N.

Trapping Rain Water

Problem:

Given a non-negative integer array. Each element represents an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, given array [1,4,0,1,0,3,1,2,0,1], the elevation map represented by it can trap 10 units of rain water.

Solution:

The brutal force solution is find the water above each of the bars. For a given bar, we can find the max bar height on the left lBound and the max bar height on the right rBound, then the amount of water above the current bar is the min(lBound, rBound) - currentHeight. For each bar, we can search the other n -1 bars to find the lBound and rBound, the total time complexity is O(N^2) and space complexity is O(1).

An improvement on the brutal force is to trade space for time. At index i, if we know the max bar height on the left is lMax[i], at index i+1, we don't have to search again, we just have to use formula lmax[i] = Math.max(lMax[i-1], height[i])

where i from 1 to height.length - 1.

We can say the same to the rMax,

rMax[i] = Math.max(rMax[i], height[i+1])

where i from arr.length - 2 to 0

That way, we get O(N) time complexity, but space complexity is O(N) as well.

With similar approach used in Largest Rectangle in Histogram, we can use a stack to follow the height values' changing trend, once we find the turning point, we take actions accordingly. In this case, we use the stack to store the decreasing sequence of the height. Once the current bar's height increase, we know we just passed a valley. The 2 bars at the stack top and the current bar formed a valley, the water holding capacity of this valley is (Math.min(height[stack(top-1)], height[current])) - height[stack(top)]) * (current - stack(top)).

import java.util.*;
public class Solution {
public static int trap(int[] arr) {
int water = 0;
Stack<Integer> lMax = new Stack<>();
lMax.push(0); //1 5 6
for(int i = 1; i < arr.length; i++) { //5
while(!lMax.isEmpty() && arr[lMax.peek()] <= arr[i]) {
int index = lMax.pop();
if(lMax.isEmpty())
break;
water += (Math.min(arr[lMax.peek()], arr[i]) - arr[index]) * (i - lMax.peek() - 1);
}
lMax.push(i);
}
return water;
}
public static void main(String...args) {
int[] arr = new int[]{1,4,0,1,0,3,1,2,0,1};
System.out.println(trap(arr));
}
}

The time complexity is O(N) and the space complexity is O(N) due to the stack.

There is a O(N) time complexity and O(1) space complexity solution.
The intuition is: we can use two pointers to mark a water container with left and right edges. The left pointer start at index 0 and the right pointer start at the last index. The two bars pointing by the 2 pointers formed a water container with capacity bottleneck at the shorter one. The 2 pointers move inward searching for the longer bars as the container's edges. If a bar is shorter than the bottleneck, the bar can hold water. If a bar is longer than the shorter container edge, the pointer moves to it thus form a taller but narrower container.

public class Solution {
public static int trap(int[] arr) {
int water = 0;
int lBound = arr[0];
int rBound = arr[arr.length - 1];
int i = 0;
int j = arr.length - 1;
while(i < j) {
if(lBound < rBound) {
while(arr[i] <= lBound) {
water += lBound - arr[i];
i++;
}
lBound = arr[i];
} else {
while(arr[j] <= rBound) {
water += rBound - arr[j];
j--;
}
rBound = arr[j];
}
}
return water;
}
public static void main(String...args) {
int[] arr = new int[]{1,4,0,1,0,3,1,2,0,1};
System.out.println(trap(arr));
}
}

Problem:

Given an n sized array of non-negative integers. The array represents a histogram made of width 1 columns. Each array element represent a column with width 1 and height equal to the array element value.

Write a function take the array as input, returns the largest rectangle in the histogram.

For Example:

Given array [2,1,5,6,2,3], the largest rectangle in the histogram is made by the column at index 2 and 3, the rectangular made by height 5 column and height 6 column has size 10, so the output is 10.

Solution:

The brutal force solution is to have a 3 layers of for loops. For each starting index i, we exam all the ending index at the right. For a pair of starting and ending index, we loop all the elements to find the minimum then calculate the area. The time complexity is O(N^3).

A better solution is to use divide and conquer. Once we found the index of the minimum height bar in an array, the solution came from 3 cases:

the largest rectangle in the histogram is (end - start) * height(minIndex)
the largest rectangle in the histogram is on the left half.
the largest rectangle in the histogram is on the right half.

In order to find the largest rectangle in the left half and right half, we can find it recursively.

If the height array is random, each left and right half divide most likely happen in the middle, the time complexity is O(NlogN).

If the height array is sorted, each left and right half happens at the edge, the performance degrades to O(N^2).

The best solution is to use a stack to help the calculation. The intuition is, when we scan the height values from left to right, if the height is increasing, we know, for sure, no matter where the the largest rectangle is, read more will only make it larger if not the same. Once the height starts to decrease, we know, for sure, the tallest bar we saw so far won't form a bigger rectangle, so we can register its value as the potential largest rectangle. Once processed the tallest bar, we then look at the second largest bar we saw so far. If the current bar is taller than the second tallest bar, then the sequence is still increasing, we want to read more to see if we can make the rectangle formed by the second tallest bar larger, otherwise, we know for sure the rectangle formed by the second tallest bar won't increase anymore, so we can register the area as the potential largest rectangle. Then we look at the third largest bar.

The algorithm is, as long as the height is increasing, we keep push the index of the height array into a stack. Once the height is decreasing, we pop out all the out of order elements in the stack in order to restore the increasing sequence in the stack. While we pop the out of order elements in the stack, we register the area of the potential largest rectangle. After we added all the height index into the stack and the stack is still not empty, we then know how to calculate the potential largest rectangles.

import java.util.*;
class Solution {

public static void main(String...args) {
int[] histo = new int[] {2,1,5,6,2,3};
System.out.println(maxArea(histo));
}

public static int maxArea(int[] histo) {
int max = -1;
//store the index of height increasing sequences
Stack<Integer> incrSeq = new Stack<>();
incrSeq.push(-1);
for(int i = 0; i < histo.length; i++) {
if(incrSeq.peek() == -1 || histo[incrSeq.peek()] <= histo[i]) {
incrSeq.push(i);
} else {
while(incrSeq.peek() != -1 && histo[incrSeq.peek()] > histo[i]) {
//calculate the hill area bounded by the two descending indexes at left (incrSeq(top - 1)) and right (i)
max = Math.max(max, histo[incrSeq.pop()] * (i - incrSeq.peek() - 1));
}
//now the height increasing sequence is restored, keep pushing
incrSeq.push(i);
}
}

int end = incrSeq.peek();
while(incrSeq.peek() != -1) {
int index = incrSeq.pop();
//clif edge area bounded by the descending indexe at left (incrSeq(top - 1)) and current index (incrSeq(top - 1))
max = Math.max(max, histo[index] * (end - index + 1));
}

return max;
}
}

The time complexity is O(N) and the space complexity is also O(N).

N-Queens II

Problem:

The N-Queens puzzle is one of the classical puzzle.

On a chess board, a queen can attack any chess on the same row, same column and on the cells in the 2 diagonal directions.

Given an integer n, we want to place n queens on a nxn chessboard, so that no two queens can attack each other.

We need to find the number of distinct solutions to the n-queens puzzle.

For Example:

given n = 4

There are two distinct solutions to put 4 queens on a 4x4 chessboard so that they can not attack each other. So the answer should be 2.

[

["xQxx", // Solution 1

"xxxQ",

"Qxxx",

"xxQx"],

["xxQx", // Solution 2

"Qxxx",

"xxxQ",

"xQxx"]

]

Solution:

This is a classic chess puzzle, we are seeking solution under constraint with try error. Track back is the technique we should use.

backtrack cell

iterate chess board cells

if cell is safe

put chess

if on last row

increase count

else

backtrack next cell

remove chess

When put a chess, we need to mark the cells on the same row, same column, same up slope diagonal and same down slope diagonal as unsafe.

These cells' can be grouped by their column and row numbers.

cells on the same row has the same row number, the column number doesn't matter, we can use an array to group them int[] row = new int[N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element row[3] = 1, then all the cells with same row number 3 are marked as 1, no matter what are their column number.
cells on the same column has the same column number, the row number doesn't matter, we can use another array to group them int[] col = new int[N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element col[2] = 1, then all the cells with the same column number 2 are marked as 1, no matter what are their row number.
cells on the same up slope diagonal has the row number decrease while the column number increase, therefore the row + col number remains the same, we can use another array to group them int[] up = new int[2*N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element up[3+2] = 1, then all the cells on the up slope diagonal are marked as 1, they are row 5 column 0, row 4 column 1, row 3 column 2, row 2 column 3, row 1 column 4 and row 0 column 5.
cells on the same down slope diagonal has both the row number and column number increase, therefore the row - col number remains the same, we can use another array to group them int[] down = new int[3*N]; Once we find a cell at row 3 and column 2 are unsafe, for example, we will mark the array element down[2-3+2*N] unsafe, then all the cells on the down slope diagonal are marked as 1. The reason we add 2*N is because row - col can be a negative number, array index has to be non-negative. The range of row - col is from -2N to N, therefore, we add 2*N and the array size is 3*N. Given N = 6 for example, the same down slope cells are [0, 1], [1, 2], [2, 3], [3, 4], [4, 5].

Actually, we don't have to back track cell by cell, once we put a queen on a cell, we know the cells on the same row are invalid, so we should move a row instead of a cell for the next move.

class Solution {
int numOfSol = 0;
public static void main(String[] args) {
int n = 4;
int[][] board = new int[n][n];
int[] cols = new int[n]; //cells on the same column
int[] up = new int[2*n]; //cells on the up slop diagonal
int[] down = new int[3*n]; //cells on the down slop diagonal
System.out.println(nQueens(board, 0, 0, cols, up, down));
}

public static int nQueens(int[][] board, int row, int count, int[] cols, int[] up, int[] down) {
int n = board.length;
for(int col = 0; col < n; col++) {
/*
System.out.println("row=" + row + " col=" + col + " count =" + count);
Arrays.stream(cols).forEach(i -> System.out.print(i + " "));
System.out.println();
Arrays.stream(up).forEach(i -> System.out.print(i + " "));
System.out.println();
Arrays.stream(down).forEach(i -> System.out.print(i + " "));
System.out.println();
*/
if(isSafe(row, col, n, cols, up, down)) {
board[row][col] = 1;
cols[col] = 1; //mark cells on the same col unsafe, cells' row doesn't matter
up[row + col] = 1; //mark cells on the same up slope unsafe, cells' row decrease, col increase,the sum is the same
down[row - col + 2*n] = 1; //mark cells on the same down slope unsafe, cells' row and col increase, row - col is the same, add 2n to prevent ArrayIndexOutOfBoundsException
if(row + 1 == n) {
count++;
printBoard(board);
System.out.println();
} else {
count = nQueens(board, row + 1, count, cols, up, down);
}
board[row][col] = 0;
cols[col] = 0; //mark the same col cells safe
up[row + col] = 0; //mark the same up slope diagonal cells safe
down[row - col + 2*n] = 0; //mark the same down slope diagonal cells safe
}
}
return count;
}

private static boolean isSafe(int row, int col, int n, int[] cols, int[] up, int[] down) {
return cols[col] + up[row + col] + down[row-col + 2*n] == 0;
}

private static void printBoard(int[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}

The time complexity's upper bound is O(N!). Before we have conclusion, we have tried all the possibilities. The way we try all the possibilities is: pick one of the columns from first row, then pick a column at the second row with constraint, then third row, so on and so forth. There are N choices at first row, then at most (ignore diagonal constraint) N - 1 choices at the second row, then N - 2 choices at the next row, finally 1 choice at the last row. The space complexity is O(N*N), it is calculated as the sum of marker arrays and board array size. Actually, if we only need the count, the board array can be omitted, the marker array has O(N) size.

Search a 2D Matrix II

Problem:

Given a m x n matrix, which has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Given a target value, return if the matrix contains this value.

For Example:

Given the following matrix:

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 9, return true.

Given target = 16, return true.

Given target = 25, return false.

Solution:

brutal force solution is loop through the 2D array, compare each single element with the target, the time complexity is O(mn), the space complexity is O(1).

The above solution didn't use the sorted property. The sorted property can be used by binary search, with some ugly code, we can hope to achieve nlogn performance.

We can also use recursive approach. One way is to start from top left, search row and column, find the boundary points, then shrink the searching range to row+1, rowboundary and col+1, colboundary.

There is an elegant and faster solution using the sorted property.

Let's start at the bottom left corner, and move up and right, if we found the target before moving out of the boundary, we return true, otherwise false. This solution is not hard to come into mind, however, the hard part is: after naturally trying the start point at top-left corner without success, instead of giving up and trying different approaches such as recursive and binary search, we should realize the approach is the best, the start point caused all the difficulties.

import java.util.*;
class Solution {
public static void main(String[] args) {
int[][] matrix = new int[][] {
{1, 4, 7, 11, 15},
{2, 5, 8, 12, 19},
{3, 6, 9, 16, 22},
{10, 13, 14, 17, 24},
{18, 21, 23, 26, 30}
};
int row = matrix.length;
int col = matrix[0].length;
System.out.println(contains(matrix, 9));
System.out.println(contains(matrix, 16));
System.out.println(contains(matrix, 20));
System.out.println(contains(matrix, 25));
System.out.println(contains(matrix, 0));
System.out.println(contains(matrix, 18));
System.out.println(contains(matrix, 15));
System.out.println(contains(matrix, 1));
}

private static boolean contains(int[][] matrix, int target) {
int rowMax = matrix.length - 1;
int colMax = matrix[0].length - 1;
int i = rowMax;
int j = 0;
while(j <= colMax && i >= 0) {
if(matrix[i][j] == target) return true;
if(matrix[i][j] > target) --i;
else ++j;
}
return false;
}
}

The time complexity is O(m+n) the space complexity is O(1).

Sudoku Solver

Problem:

Write a program to solve a Sudoku puzzle.

Sudoku is a popular puzzle game. The goal of Sudoku is to fill a 9×9 grid with numbers so that each row, column and 3×3 section contain all of the digits between 1 and 9.

Solution:

This is a typical backtracking problem. For current cell, we try numbers from 1 to 9, if a number is valid, then we recursively try the rest of the cells. If the current number is invalid or the rest of the cells can not be filled correctly, we try the next number.

class Solution {
public static boolean sudoku(int[][] board, int n) {
int N = board.length;
if(n > N * N - 1)
return true;
int i = n/N;
int j = n%N;
if(board[i][j] > 0) { //skip none-empty cell
return sudoku(board, n+1);
} else {
for(int k = 1; k <= N; k++) {
board[i][j] = k;
if(isValid(board, i, j) && sudoku(board, n+1)) {
return true;
}
}
board[i][j] = -1; //put it back
return false;
}
}

private static boolean isValid(int[][] board, int row, int col) {
for(int i = 0; i < row; i++) { //cells above
if(board[i][col] == board[row][col])
return false;
}
for(int j = 0; j < col; j++) { //cells left
if(board[row][j] == board[row][col])
return false;
}
for(int i = 3 * (row/3); i < 3 * (row/3) + 3; i++) {
for(int j = 3 * (col/3); j < 3 * (col/3) + 3; j++) {
if(board[i][j] > 0 && !(i == row && j == col) && board[i][j] == board[row][col]) {
return false;
}
}
}
return true;
}

public static void main(String[] args) {
int[][] board = new int[9][9];
board[2][2] = 4;
printBoard(board);
System.out.println(sudoku(board, 0));
printBoard(board);
}
private static void printBoard(int[][] board) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[i].length; j++) {
System.out.print(String.format("%3d", board[i][j]));
}
System.out.println();
}
}
}

Since the board size is fixed, there is no big O with N notation.

The time complexity has upper boundary (9^81)*27. The number 9^81 is because for each cell, we can have 9 options, there are 81 cells. For each option, check validity took 27 compares. We check at most 9 same row cells, 9 same column cells and 9 same cubic cells. It is upper bound because not all 81 cells are empty and we only have to compare the cells above and left of the current cell and we compare few cells for those invalid options.

The space complexity is 81, the size of board.

We can trade space for time. If we can keep updating all the allowed numbers for the 81 cells at each step, we don't have to try all the 9 numbers. We only have to try 9! numbers for the 9 cells in a row. There are 9 rows, so the total time complexity will be (9!)^9*81, which is substantially faster than the simple backtrack code above. The space complexity will be more than 81*10, besides associate a value to each cell, we have to associate an extra set to each cell for the allowed numbers. Set's object overhead and references will make 10 fold memory increase an under-estimate.

Permutations

Problem:

Given a collection of distinct letters, return all possible permutations.

For Example:

Given: [a,b,c]
the permutations are:
[
[a,b,c],
[a,c,b],
[b,a,c],
[b,c,a],
[c,a,b],
[c,b,a]
]

Solution:

With backtracking, we can find the permutations.

There are N! number of possible permutations, the time complexity will be bigger than O(N!). It will be bigger because we have to generate all those temporary substrings as parameters for recursive call. The total number of possible substrings is sum(P(N,k)) where k range from 1 to N. The sum(P(N,k)) is the number of all possible substrings by randomly picking k letter from total of N letters to form a string.
since P(N,k) = N!/(N-k)! <= N!, the sum(P(N,k)) <= N*N!.
As a result, the time complexity is between O(N!) and O(N*N!)

The since we generated many substrings as parameters for recursive calls, and java string pool did internal caching, the space complexity is bounded by the total number of possible substrings, which is less than O(N*N!).

class Solution {
public static void permutations(String s, String remains) {
if(remains.isEmpty()) {
System.out.println(s);
return;
}
for(int i = 0; i < remains.length(); i++) {
char c = remains.charAt(i);
permutations(s + c, remains.substring(0, i) + remains.substring(i+1)); //take out a character
}
}

public static void main(String[] args) {
permutations("", "abc");
}
}

time complexity O(N!) to O(N*N!), space complexity O(N*N!)

Use string to do the permutations is easy, however it took extra space to store temporary strings, we can use a reusable char array to avoid extra space.

class Solution {
public static void permutations(char[] orig, int n) {
if(n == orig.length) {
System.out.println(new String(orig));
return;
}
for(int i = n; i < orig.length; i++) {
swap(orig, n, i);
permutations(orig, n+1);
swap(orig, n, i); //restore original array
}
}

private static void swap(char[] orig, int i, int j) {
char tmp = orig[i];
orig[i] = orig[j];
orig[j] = tmp;
}

public static void main(String[] args) {
permutations("abc".toCharArray(), 0);
}
}

time complexity O(N!) to O(N*N!), space complexity O(N) for the char array.

see also: number permutations with restrictions

Find two swapped elements in an almost sorted array

Problem:

Find two swapped elements in an almost sorted array.
For example
given array [1,4,3,2,5,6]
the answer is:
4 and 2

Solution:

this is a classical problem that can be achieved with one pass and no extra space.

class Solution {
public static void main(String...args) {
int[] a = new int[]{1,4,3,2,5,6};
int x = -1;
int y = -1;
for(int i = 0; i < a.length - 1; i++) {
if(a[i] > a[i+1]) {
y = a[i + 1];
if(x == -1) x = a[i];
else break;
}
}
System.out.println(x + "," + y);
}
}

Time complexity O(N), space complexity O(1).

This is a simple problem, but the same principle can be used to solve harder problems such as recover binary search tree.

Partition to K Equal Sum Subsets

Problem

Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4

Output: True

Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

1 <= k <= len(nums) <= 16.

0 < nums[i] < 10000.

Solution

Prove an array is able to divide to K equal sum subsets won't be easy at first sight, so let's first rule out those cases that can not be divided.

sum%k != 0
the largest element is larger than sum/k

Elements equal to target can be put into one array by itself, elements equal 0 can be put anywhere.

For the elements left, unfortunately, we need to enumerate all the possible cases until we found the solution. Assuming there are n elements left. How many combinations we need to try?

This is equivalent to a statistics problem: how many possible ways of putting n balls into k buckets, each bucket must have at least one ball.

For the statistics problem, we first first pick n-k balls, randomly put them into k buckets. Each ball has k choices, the total choice is k^(n-k). After that, there are only k balls left, there are k! ways of put k balls into k bucket. So that set high boundary for our time complexity O(k^(n-k)*k!).

There are several ways of solving the above statistics problem.

Approach one could be. We enumerate all the subsets excluding the self array and empty array. The cost will be 2^N. Then we filter out all those with sum equal to target. Then we randomly pick k of them, test if their elements add up to the original array.

Approach two could be. We pick one element i at a time from the n elements, try to put into one of the bucket m from m = 0 to k-1. If success, we pick another element ++i, try to put into one of bucket m from m = 0 to k-1. If fail, we remove the element i from bucket m, return false. Recursively doing this will iterate through all the possible scenarios. The exit condition is we have tried the last element in i in the array.

Let's code according to approach two.

public class KEqualSum {

public static boolean canDo(int[] a, int k) {

Arrays.sort(a);

int sum = Arrays.stream(a).sum();

if(sum%k!=0) return false;

if(sum == 0 && a.length >= k) return true;

int target = sum/k;

int i = a.length-1;

int j = 0;

if(a[i] > target) return false;

while(i >= 0 && a[i] == target) {

i--;

k--;

}

while(j <= i && a[i] == 0) {

j++;

}

int[] sums = new int[k];

return canDivide(a, sums, i, j, target);

}

private static boolean canDivide(int[] a, int[] sums, int curIndex, int stopIndex, int target) {

if(curIndex < stopIndex) return true;

for(int i = 0; i < sums.length; i++) {

if(sums[i] + a[curIndex] <= target) {

sums[i] += a[curIndex];

if(canDivide(a, sums, --curIndex, stopIndex, target)) return true;

sums[i] = a[curIndex];

}

return false;

}

public static void main(String...args) {

int[] a = {4, 3, 2, 3, 5, 2, 1, 0, 0, 0, 0};

int k = 4;

System.out.println(canDo(a, k));

}

Time cost O(k^(n-k)*k!), space cost O(N).

Problem

Solution

Problem

Solution

Problem

Solution

Problem

Solution

Problem:

Solution:

Problem:

Solution:

Problem:

Problem:

Solution:

Problem:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

Problem:

Solution:

See also:

Problem:

Solution:

Problem:

Solution:

See also:

Solution:

Problem:

Solution:

See also:

Problem:

Solution:

Problem:

Solution:

Problem

Solution