public Alphabet(String alpha) {
    // check that alphabet contains no duplicate chars
    boolean[] unicode = new boolean[Character.MAX_VALUE];
    for (int i = 0; i < alpha.length(); i++) {
        char c = alpha.charAt(i);
        if (unicode[c])
            throw new IllegalArgumentException("Illegal alphabet: repeated character = '" + c + "'");
        unicode[c] = true;
    }

    alphabet = alpha.toCharArray();
    R = alpha.length();
    inverse = new int[Character.MAX_VALUE];
    for (int i = 0; i < inverse.length; i++)
        inverse[i] = -1;

    // can't use char since R can be as big as 65,536
    for (int c = 0; c < R; c++)
        inverse[alphabet[c]] = c;
}

public int toIndex(char c) {
    if (c >= inverse.length || inverse[c] == -1) {
        throw new IllegalArgumentException("Character " + c + " not in alphabet");
    }
    return inverse[c];
}

public char toChar(int index) {
    if (index < 0 || index >= R) {
        throw new IllegalArgumentException("index must be between 0 and " + R + ": " + index);
    }
    return alphabet[index];
}

// %java Count 0123456789 < pi.txt
public static void main(String[] args) {
    Alphabet alphabet = new Alphabet(args[0]);
    final int R = alphabet.radix();
    int[] count = new int[R]; // just need an array of R (for each character)
    while (StdIn.hasNextChar()) {
        char c = StdIn.readChar();
        if (alphabet.contains(c))
            count[alphabet.toIndex(c)]++;
    }
    for (int c = 0; c < R; c++)
        StdOut.println(alphabet.toChar(c) + " " + count[c]);
}

public void leftRotate(int[] nums, int d, int n) {
  for (int i = 0; i < d; i++) {
    int j = 0, temp = nums[0];
    for (j = 0; j < n - 1; j++) {
      nums[j] = nums[j + 1];
    }
    nums[j] = temp;
  }
}

public void rightRotate(int[] nums, int d) {
  d %= nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, d - 1);
  reverse(nums, d, nums.length - 1);
}
private void reverse(int[] nums, int start, int end) {
  while (start < end) {
    swap(nums, start++, end--);
  }
}
private void swap(int[] nums, int i, int j) {
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

public void moveZeroes(int[] nums) {
  for (int insertNonZeroAt = 0, i = 0; i < nums.length; i++) {
    if (nums[i] != 0) {
      // reduce extra swap
      if (i != insertNonZeroAt) {
        int temp = nums[i];
        nums[i] = nums[insertNonZeroAt];
        nums[insertNonZeroAt] = temp;
      }
      insertNonZeroAt++;
    }
  }
}

public void wiggleSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        if ((i % 2 == 0 && nums[i - 1] < nums[i]) || (i % 2 != 0 && nums[i - 1] > nums[i])) {
            int tmp = nums[i];
            nums[i] = nums[i - 1];
            nums[i - 1] = tmp;
        }
    }
}

public void evenOddSort(int[] nums) {
  int even = 0, odd = nums.length - 1;
  while (even < odd) {
    if (nums[even] % 2 == 0) {
      even++;
    } else {
      // only swap for even num!
      if (nums[odd] % 2 == 0) {
        int temp = nums[even];
        nums[even] = nums[odd];
        nums[odd] = temp;
      }
      odd--;
    }
  }
}

public boolean canPlaceFlowers(int[] flowerbed, int n) {
  int i = 0, count = 0;
  while (i < flowerbed.length) {
    if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0)
        && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
      flowerbed[i++] = 1;
      count++;
    }
    if (count >= n) // stop as soon as count becomes equal to n
      return true;
    i++;
  }
  return false;
}

public static int[] squareSort(int[] array) {
  if (array == null || array.length == 0)
    return new int[0];
  int[] result = new int[array.length];
  int i = 0, j = 0;
  // while (i < array.length && array[i] < 0)
  // i++;
  i = binarySearch(array, 0);
  j = i - 1;
  int index = 0;
  while (j >= 0 || i < array.length) {
    if (j < 0) {
      result[index++] = array[i] * array[i];
      i++;
    } else if (i >= array.length) {
      result[index++] = array[j] * array[j];
      j--;
    } else if (Math.abs(array[j]) > array[i]) {
      result[index++] = array[i] * array[i];
      i++;
    } else {
      result[index++] = array[j] * array[j];
      j--;
    }
  }
  return result;
}

private static int binarySearch(int[] array, int target) {
  int left = 0, right = array.length - 1;
  // find the value >= target
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (target == array[mid])
      return mid;
    else if (target < array[mid])
      right = mid - 1;
    else
      left = mid + 1;
  }
  return left;
}

public static void main(String[] args) {
  assert Arrays.equals(squareSort(new int[] { -4, 1, 3, 5 }), new int[] { 1, 9, 16, 25 });
  assert Arrays.equals(squareSort(new int[] { 0, 1, 3, 5 }), new int[] { 0, 1, 9, 25 });
  assert Arrays.equals(squareSort(new int[] { -5, -4, -1 }), new int[] { 1, 16, 25 });
  assert Arrays.equals(squareSort(new int[] { -4, -1, 0, 3, 5, 5 }), new int[] { 0, 1, 9, 16, 25, 25 });
}

public boolean canReachEnd(int[] maxAdvancedSteps) {
  int furthestReachSoFar = 0, lastIndex = maxAdvancedSteps.length - 1;
  for (int i = 0; i <= furthestReachSoFar && furthestReachSoFar < lastIndex; i++) {
    furthestReachSoFar = Math.max(furthestReachSoFar, maxAdvancedSteps[i] + i);
  }
  return furthestReachSoFar >= lastIndex;
}

public List<List<Integer>> generatePascalTriangle(int numRows) {
  List<List<Integer>> result = new ArrayList<>();
  for (int i = 0; i < numRows; i++) {
    List<Integer> currRow = new ArrayList<>();
    for (int j = 0; j <= i; j++) {
      if (0 < j && j < i)
        currRow.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
      else
        currRow.add(1);
    }
    result.add(currRow);
  }
  return result;
}

public int[] twoSum(int[] numbers, int target) {
  int[] result = new int[2];
  Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  for (int i = 0; i < numbers.length; i++) {
    if (map.containsKey(target - numbers[i])) {
      result[1] = i;
      result[0] = map.get(target - numbers[i]);
      return result;
    }
    map.put(numbers[i], i);
  }
  return result;
}

public int[] twoSum2(int[] numbers, int target) {
  int i = 0, j = numbers.length - 1;
  while (i < j) {
    int sum = numbers[i] + numbers[j];
    if (sum == target)
      return new int[] { i + 1, j + 1 };
    else if (sum < target)
      i++;
    else
      j--;
  }
  return new int[] { -1, -1 };
}

public class TwoSum {
	Map<Integer, Integer> map = new HashMap<Integer, Integer>();

	// Add the number to an internal data structure.
	public void add(int number) {
		if (map.containsKey(number)) {
			map.put(number, map.get(number) + 1);
		} else {
			map.put(number, 1);
		}
	}

	// Find if there exists any pair of numbers which sum is equal to the value.
	public boolean find(int value) {
		Iterator<Integer> iter = map.keySet().iterator();
		while (iter.hasNext()) {
			int num1 = iter.next();
			int num2 = value - num1;
			if (map.containsKey(num2)) {
				if (num1 != num2 || map.get(num2) >= 2) {
					return true;
				}
			}
		}
		return false;
	}
}

public List<List<Integer>> threeSum(int[] nums) {
	Arrays.sort(nums);
	List<List<Integer>> list = new LinkedList<>();
	for (int i = 0; i < nums.length - 2; i++) {
		if (i > 0 && nums[i] == nums[i - 1]) // skip duplicates
			continue;
		int lo = i + 1, hi = nums.length - 1;
		while (lo < hi) {
			int sum = nums[i] + nums[lo] + nums[hi];
			if (sum == 0) {
				list.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
				while (lo < hi && nums[lo] == nums[lo + 1]) // skip duplicates
					lo++;
				while (lo < hi && nums[hi] == nums[hi - 1]) // skip duplicates
					hi--;
				lo++;
				hi--;
			} else if (sum < 0)
				lo++;
			else
				hi--;
		}
	}
	return list;
}

  // Divide and conquer O(nlog(n))
  public int countRangeSum(int[] nums, int lower, int upper) {
    // easy to cover edge cases with one extra space
    long[] sums = new long[nums.length + 1];
    // calculate prefix sums
    for (int i = 1; i < sums.length; i++) {
      sums[i] = sums[i - 1] + nums[i - 1];
    }
    return divide(sums, new long[sums.length], 0, sums.length - 1, lower, upper);
  }

  public int divide(long[] sums, long[] temp, int low, int high, int lower, int upper) {
    if (low >= high)
      return 0;

    int count = 0, mid = (low + high + 1) / 2;
    count += divide(sums, temp, low, mid - 1, lower, upper);
    count += divide(sums, temp, mid, high, lower, upper);
    count += merge(sums, temp, low, mid, high, lower, upper);
    return count;
  }

  public int merge(long[] sums, long[] temp, int low, int mid, int high, int lower, int upper) {
    // low~mid and mid+1~high are both sorted at this point
    // Scan the left half and pair with right half
    int count = 0, start = mid, end = mid;
    for (int i = low; i < mid; i++) {
      while (start <= high && sums[start] - sums[i] < lower)
        start++;
      while (end <= high && sums[end] - sums[i] <= upper)
        end++;
      count += end - start;
    }

    // mid belongs to the right half
    int current = low, left = low, right = mid;
    while (left < mid && right <= high) {
      if (sums[left] <= sums[right]) {
        temp[current++] = sums[left++];
      } else {
        temp[current++] = sums[right++];
      }
    }
    // copy the rest of left half
    while (left < mid) {
      temp[current++] = sums[left++];
    }
    // copy the rest of right half
    while (right <= high) {
      temp[current++] = sums[right++];
    }

    // copy sorted temp (low~high) to sums
    System.arraycopy(temp, low, sums, low, high - low + 1);

    return count;
  }

public class MovingAverage {
    private int[] window;
    private int count = 0, insert = 0;
    private long sum = 0;

    public MovingAverage(int size) {
        if (size <= 0)
            throw new IllegalArgumentException();
        window = new int[size];
    }

    public double next(int value) {
        if (count < window.length)
            count++;
        sum -= window[insert];
        sum += value;
        window[insert] = value;
        insert = (insert + 1) % window.length;
        return (double) sum / count;
    }
}

public int kEmptySlots(int[] flowers, int k) {
  int[] days = new int[flowers.length];
  for (int i = 0; i < flowers.length; i++)
    days[flowers[i] - 1] = i + 1;
  int left = 0, right = k + 1, minDay = Integer.MAX_VALUE;
  for (int i = 0; right < days.length; i++) {
    if (days[i] < days[left] || days[i] <= days[right]) {
      if (i == right)
        minDay = Math.min(minDay, Math.max(days[left], days[right])); // we get a valid subarray
      left = i;
      right = k + 1 + i;
    }
  }
  return (minDay == Integer.MAX_VALUE) ? -1 : minDay;
}

public class ShuffleAnArray {
	private Random random;

	private int[] array;
	private int[] original;

	private int[] runningSample;
	private int numSeenSoFar;

	public ShuffleAnArray(int[] nums, int sampleSize) {
		this.random = new Random();

		this.array = nums;
		this.original = nums.clone();

		this.runningSample = new int[sampleSize];
	}

	public int[] reset() {
		array = original;
		original = original.clone();

		numSeenSoFar = 0;
		Arrays.fill(runningSample, 0);
		return array;
	}

	public int[] shuffle() {
		for (int i = 0; i < array.length; i++) {
			swapAt(i, i + random.nextInt(array.length - i));
		}
		return array;
	}

	public int[] shuffle(int k) {
		for (int i = 0; i < k; i++) {
			swapAt(i, i + random.nextInt(array.length - i));
		}
		return Arrays.copyOfRange(array, 0, k);
	}

	public int[] streamShuffle(Iterator<Integer> sequence) {
		while (sequence.hasNext()) {
			int x = sequence.next();
			numSeenSoFar++;
			// fill up the running sample first
			if (numSeenSoFar < runningSample.length) {
				runningSample[numSeenSoFar - 1] = x;
			} else {
				int i = random.nextInt(numSeenSoFar);
				if (i < runningSample.length)
					runningSample[i] = x;
			}
		}
		return runningSample;
	}

	private void swapAt(int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

}

public List<Integer> topKFrequent(int[] nums, int k) {
  List<Integer> result = new ArrayList<>();
  if (nums.length == 0)
    return result;

  // Avoid using hash map
  int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] < min)
      min = nums[i];
    if (nums[i] > max)
      max = nums[i];
  }
  int[] data = new int[max - min + 1];
  for (int i = 0; i < nums.length; i++) {
    data[nums[i] - min]++;
  }

  // Index is frequency
  @SuppressWarnings("unchecked")
  List<Integer>[] bucket = new ArrayList[nums.length + 1];
  for (int i = 0; i < data.length; i++) {
    if (data[i] > 0) {
      if (bucket[data[i]] == null) {
        bucket[data[i]] = new ArrayList<Integer>();
      }
      bucket[data[i]].add(i + min);
    }
  }
  for (int i = nums.length; i >= 0 && result.size() < k; i--) {
    if (bucket[i] != null)
      result.addAll(bucket[i]);
  }
  return result;
}

public List<Integer> randomSubset(int n, int k) {
  Map<Integer, Integer> changedElements = new HashMap<>();
  Random randIdxGen = new Random();

  for (int i = 0; i < k; i++) {
    int randIdx = i + randIdxGen.nextInt(n - i);
    Integer ptr1 = changedElements.get(randIdx);
    Integer ptr2 = changedElements.get(i);
    if (ptr1 == null && ptr2 == null) {
      changedElements.put(randIdx, i);
      changedElements.put(i, randIdx);
    } else if (ptr1 == null && ptr2 != null) {
      changedElements.put(randIdx, ptr2);
      changedElements.put(i, randIdx);
    } else if (ptr1 != null && ptr2 == null) {
      changedElements.put(i, ptr1);
      changedElements.put(randIdx, i);
    } else {
      changedElements.put(i, ptr1);
      changedElements.put(randIdx, ptr2);
    }
  }

  List<Integer> result = new ArrayList<>(k);
  for (int i = 0; i < k; i++) {
    result.add(changedElements.get(i));
  }
  return result;
}

public int nonuniformRandomNumber(List<Integer> values, List<Double> probabilities) {
  List<Double> prefixSumOfProbabilities = new ArrayList<>();
  prefixSumOfProbabilities.add(0.0);
  for (double p : probabilities) {
    prefixSumOfProbabilities.add(prefixSumOfProbabilities.get(prefixSumOfProbabilities.size() - 1) + p);
  }

  Random r = new Random();
  // Get a random number in [0.0,1.0).
  final double uniform01 = r.nextDouble();
  // Find the index of the interval that uniform01 lies in.
  int it = Collections.binarySearch(prefixSumOfProbabilities, uniform01);
  if (it < 0) {
    // We want the index of the first element in the array which is greater than the key.
    //
    // When a key is not present in the array, Collections.binarySearch() returns the
    // negative of (1 plus the smallest index) whose entry is greater than the key.
    //
    // Therefore, if the return value is negative, by taking its absolute value minus 1 and
    // substracting 1 from it, we get the desired index.
    final int intervalIdx = (Math.abs(it) - 1) - 1;
    return values.get(intervalIdx);
  } else {
    // We have it >= 0, i.e., uniform01 equals an entry in prefixSumOfProbabilities.
    //
    // Because we uniform01 is a random double, the probability of it equalling an endpoint
    // in prefixSumOfProbabilities is exceedingly low.
    return values.get(it);
  }
}

public class RandomPickIndex {
	int[] nums;
	Random random;

	public RandomPickIndex(int[] nums) {
		this.nums = nums;
		this.random = new Random();
	}

	public int pick(int target) {
		int result = -1;
		int count = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] == target) {
				count++;
				if (random.nextInt(count) == 0) {
					// don't return here due to nextInt(1) is always zero!
					result = i;
				}
			}
		}
		return result;
	}
}

public class RandomPickWithWeight {
	List<Integer> psum = new ArrayList<>();
	int tot = 0;
	Random rand = new Random();

	public RandomPickWithWeight(int[] w) {
		for (int x : w) {
			tot += x;
			psum.add(tot);
		}
	}

  // find the lowest index such that targ < p[x]
	public int pickIndex() {
		int targ = rand.nextInt(tot);

		int lo = 0;
		int hi = psum.size() - 1;
		while (lo != hi) { // to the same position
			int mid = (lo + hi) / 2;
			if (targ >= psum.get(mid))
				lo = mid + 1;
			else
				hi = mid;
		}
		return lo;
	}

  // or use tree map to get the ceiling value.
	public int pickIndex2() {
		int key = map.ceilingKey(rand.nextInt(tot) + 1);
		// int key= map.heigherKey(rnd.nextInt(cnt));
		return map.get(key);
	}
}

public class RandomPickWithBlacklist {
  private Random random;
  private int whitelistLen;
  private Map<Integer, Integer> map;

  public RandomPickWithBlacklist(int N, int[] blacklist) {
    map = new HashMap<>();
    random = new Random();
    whitelistLen = N - blacklist.length;
    Set<Integer> set = new LinkedHashSet<>();
    for (int i = whitelistLen; i < N; i++)
      set.add(i);
    for (int b : blacklist) {
      if (b >= whitelistLen)
        set.remove(b);
    }
    Iterator<Integer> iterator = set.iterator();
    for (int b : blacklist) {
      if (b < whitelistLen)
        map.put(b, iterator.next());
    }
  }

  public int pick() {
    int k = random.nextInt(whitelistLen);
    return map.getOrDefault(k, k);
  }
}

public int findPeakElement(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1])
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

public int[] singleNumberIII(int[] nums) {
  int diff = 0;
  for (int num : nums) {
    diff ^= num;
  }

  // Extract the lowest set bit of x which can be used to divide numbers into two groups.
  diff &= ~(diff - 1); // or diff &= -diff;

  // Each group should have one expected element
  int[] result = { 0, 0 };
  for (int num : nums) {
    if ((num & diff) == 0)
      result[0] ^= num;
    else
      result[1] ^= num;
  }

  return result;
}

public void nextPermutation(int[] nums) {
  if (nums == null || nums.length < 1)
    return;

  int position = nums.length - 2;
  while (position >= 0 && nums[position] >= nums[position + 1]) {
    position--;
  }

  if (position == -1) {
    reverse(nums, 0, nums.length - 1);
    return;
  }

  // this position's value should be swapped by the most closed one
  for (int i = nums.length - 1; i > position; i--) {
    if (nums[i] > nums[position]) {
      swap(nums, position, i);
      break;
    }
  }

  // reverse all items after the position
  reverse(nums, position + 1, nums.length - 1);
}

private void swap(int[] nums, int i, int j) {
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

private void reverse(int[] nums, int start, int end) {
  while (start < end) {
    swap(nums, start++, end--);
  }
}

public void solveSudoku(char[][] board) {
  doSolve(board, 0, 0);
}

private boolean doSolve(char[][] board, int row, int col) {
  // Note: must reset col here as we need to loop through all rest cells!
  for (int i = row; i < 9; i++, col = 0) {
    for (int j = col; j < 9; j++) {
      if (board[i][j] != '.')
        continue;
      for (char num = '1'; num <= '9'; num++) {
        if (isValid(board, i, j, num)) {
          board[i][j] = num;
          if (doSolve(board, i, j + 1))
            return true;
          board[i][j] = '.'; // backtracking
        }
      }
      return false;
    }
  }
  return true;
}

private boolean isValid(char[][] board, int row, int col, char num) {
  // Block no. is i/3, first element is i/3*3
  int blockRow = (row / 3) * 3, blockCol = (col / 3) * 3;
  for (int i = 0; i < 9; i++)
    if (board[i][col] == num || board[row][i] == num || board[blockRow + i / 3][blockCol + i % 3] == num)
      return false;
  return true;
}

// Approach1: Simulation Spiral, always moving right
public List<Integer> spiralOrder(int[][] matrix) {
  List<Integer> result = new ArrayList<>();
  if (matrix.length == 0)
    return result;
  int[][] shift = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
  int m = matrix.length, n = matrix[0].length;
  boolean[][] seen = new boolean[m][n];
  int row = 0, col = 0, dir = 0;
  for (int i = 0; i < m * n; i++) {
    result.add(matrix[row][col]);
    seen[row][col] = true;
    int nextRow = row + shift[dir][0], nextCol = col + shift[dir][1];
    // seen[nextRow][nextCol] == true means moving to next right neighbor
    if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || seen[nextRow][nextCol]) {
      dir = (dir + 1) % 4;
      nextRow = row + shift[dir][0];
      nextCol = col + shift[dir][1];
    }
    row = nextRow;
    col = nextCol;
  }
  return result;
}

// Approach2: Layer-by-Layer
  public List<Integer> spiralOrder2(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix.length == 0)
      return result;
    int r1 = 0, r2 = matrix.length - 1;
    int c1 = 0, c2 = matrix[0].length - 1;
    while (r1 <= r2 && c1 <= c2) {
      for (int c = c1; c <= c2; c++)
        result.add(matrix[r1][c]);
      r1++;
      for (int r = r1; r <= r2; r++)
        result.add(matrix[r][c2]);
      c2--;
      if (r1 <= r2 && c1 <= c2) {
        for (int c = c2; c >= c1; c--)
          result.add(matrix[r2][c]);
        r2--;
        for (int r = r2; r >= r1; r--)
          result.add(matrix[r][c1]);
        c1++;
      }
    }
    return result;
  }

public void setMatrixZeroes(int[][] matrix) {
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
    return;
  int m = matrix.length, n = matrix[0].length;
  boolean row = false, col = false;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (matrix[i][j] == 0) {
        matrix[0][j] = 0;
        matrix[i][0] = 0;
        if (i == 0)
          row = true;
        if (j == 0)
          col = true;
      }
    }
  }
  for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
      if (matrix[i][0] == 0 || matrix[0][j] == 0)
        matrix[i][j] = 0;
    }
  }
  if (row) {
    for (int j = 0; j < n; j++)
      matrix[0][j] = 0;
  }
  if (col) {
    for (int i = 0; i < m; i++)
      matrix[i][0] = 0;
  }
}

/**
 * Given an integer array nums, return the length of the longest strictly increasing subsequence.
 * 
 * A subsequence is a sequence that can be derived from an array by deleting some or no elements
 * without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of
 * the array [0,3,1,6,2,2,7].
 * 
 * <br>
 * 
 * Example 1:
 * 
 * Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is
 * [2,3,7,101], therefore the length is 4.
 * 
 * <br>
 * 
 * Example 2:
 * 
 * Input: nums = [0,1,0,3,2,3] Output: 4
 * 
 * <br>
 * 
 * Example 3:
 * 
 * Input: nums = [7,7,7,7,7,7,7] Output: 1
 * 
 * @author lchen676
 *
 */
public class LongestIncreasingSubsequence {
  /**
   * Intelligently build a pile of subsequences with binary search.
   * 
   * Time complexity: O(Nlog(N))
   */
  public int lengthOfLIS(int[] nums) {
    List<Integer> sub = new ArrayList<>();
    sub.add(nums[0]);

    for (int i = 1; i < nums.length; i++) {
      int num = nums[i];
      if (num > sub.get(sub.size() - 1)) {
        sub.add(num);
      } else {
        int j = binarySearch(sub, num);
        sub.set(j, num);
      }
    }

    return sub.size();
  }

  private int binarySearch(List<Integer> sub, int num) {
    int left = 0;
    int right = sub.size() - 1;
    int mid = (left + right) / 2;

    while (left < right) {
      mid = (left + right) / 2;
      if (sub.get(mid) == num) {
        return mid;
      }

      if (sub.get(mid) < num) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return left;
  }

  /**
   * Dynamic programming, time complexity: O(N^2)
   * 
   * dp[i] represents the length of the longest increasing subsequence that ends with the element at
   * index i.
   */
  public int lengthOfLIS2(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);

    for (int i = 1; i < nums.length; i++) {
      for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
    }

    int longest = 0;
    for (int c : dp) {
      longest = Math.max(longest, c);
    }

    return longest;
  }

}

/**
 * You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width
 * and the height of an envelope.
 * 
 * One envelope can fit into another if and only if both the width and height of one envelope are
 * greater than the other envelope's width and height.
 * 
 * Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).
 * 
 * Note: You cannot rotate an envelope.
 *
 * Example 1:
 * 
 * Input: envelopes = [[5,4],[6,4],[6,7],[2,3]] <br>
 * Output: 3 <br>
 * Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
 * 
 * https://leetcode.com/problems/russian-doll-envelopes/
 * 
 */
public class RussianDollEnvelopes {
  public int maxEnvelopes(int[][] envelopes) {
    // Check envelopes emptiness if neccessary

    // Sort increasing on the first dimension, and decreasing on the second dimension, so that two
    // envelopes that are equal in the first dimension can never be in the same increasing subsequence.
    Arrays.sort(envelopes, (a, b) -> (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));

    // dp is an array such that dp[i] is the smallest element that ends an increasing subsequence of
    // length i + 1. Whenever we encounter a new element e, we binary search inside dp to find the
    // largest index i such that e can end that subsequence. We then update dp[i] with e.
    int length = 0;
    int dp[] = new int[envelopes.length];
    for (int[] envelope : envelopes) {
      int height = envelope[1];
      if (length == 0 || height > dp[length - 1]) {
        dp[length++] = height;
      } else {
        int index = Arrays.binarySearch(dp, 0, length, height);
        dp[index < 0 ? -(index + 1) : index] = height;
      }
    }
    return length;
  }
}

/**
 * Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous)
 * subarray of arr. Since the answer may be large, return the answer modulo 10^9 + 7.
 * 
 * <pre>
 * Example 1:
 * 
 * Input: arr = [3,1,2,4]
 * Output: 17
 * Explanation: 
 * Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
 * Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
 * Sum is 17.
 * </pre>
 * 
 * https://leetcode.com/problems/sum-of-subarray-minimums/
 */
public class SumofSubarrayMinimums {

  // Use monotonic stack to track nums
  public int sumSubarrayMins(int[] arr) {
    Deque<int[]> stack = new LinkedList<>();
    long totalSum = 0, minPreSum = 0;
    for (int num : arr) {
      int count = 1;
      while (!stack.isEmpty() && stack.peek()[0] > num) {
        int[] cur = stack.pop();
        count += cur[1];
        minPreSum -= cur[0] * cur[1]; // deduct invalid numbers
      }
      stack.push(new int[] { num, count });
      minPreSum += count * num;
      totalSum += minPreSum;
    }
    return (int) (totalSum % (1e9 + 7));
  }

  // Use monotonic stack to track indices
  public int sumSubarrayMins2(int[] arr) {
    long sum = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i <= arr.length; i++) {
      while (!stack.isEmpty() && (i == arr.length || arr[stack.peek()] > arr[i])) {
        int mid = stack.pop(); // middle min pilliar
        int left = mid - (stack.isEmpty() ? -1 : stack.peek());
        int right = i - mid;
        sum += (long) arr[mid] * left * right;
      }
      stack.push(i);
    }
    return (int) (sum % (1e9 + 7));
  }

  // Use monotonic stack to track indices
  public int sumSubarrayMins3(int[] arr) {
    long sum = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1); // leverage a dummy index
    for (int i = 0; i <= arr.length; i++) {
      while (stack.peek() != -1 && (i == arr.length || arr[stack.peek()] > arr[i])) {
        int mid = stack.pop(); // middle min pilliar
        int left = mid - stack.peek();
        int right = i - mid;
        sum += (long) arr[mid] * left * right;
      }
      stack.push(i);
    }
    return (int) (sum % (1e9 + 7));
  }

}

/**
 * Given an integer array nums and an integer k, return the number of good subarrays of nums.
 * 
 * A good array is an array where the number of different integers in that array is exactly k.
 * 
 * For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3. A subarray is a contiguous part
 * of an array.
 * 
 * 
 * <pre>
 * Example 1:
 * 
 * Input: nums = [1,2,1,2,3], k = 2
 * Output: 7
 * Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
 * </pre>
 *
 */
public class SubarraysWithKDifferentIntegers {

  /**
   * https://leetcode.com/problems/subarrays-with-k-different-integers/discuss/235235/C%2B%2BJava-with-picture-prefixed-sliding-window
   * 
   * Intuition: If the subarray [left, i] contains K unique numbers, and first prefix numbers also
   * appear in [left + prefix, i] subarray, we have total 1 + prefix good subarrays. For example,
   * there are 3 unique numers in [1, 2, 1, 2, 3]. First two numbers also appear in the remaining
   * subarray [1, 2, 3], so we have 1 + 2 good subarrays: [1, 2, 1, 2, 3], [2, 1, 2, 3] and [1, 2, 3].
   */
  public int subarraysWithKDistinct(int[] nums, int k) {
    int result = 0, prefix = 0;
    int[] counts = new int[nums.length + 1];
    int left = 0, count = 0;
    for (int i = 0; i < nums.length; i++) {
      // Only count for the first time
      if (counts[nums[i]]++ == 0) {
        count++;
      }
      // Remove the only left one when exceeded windows size
      if (count > k) {
        counts[nums[left++]]--;
        count--;
        prefix = 0;
      }
      if (count == k) {
        // Remove until the number on the left appears only once
        while (counts[nums[left]] > 1) {
          counts[nums[left++]]--;
          prefix++; // increase prefix
        }
        // Collect all good subarrys
        result += prefix + 1;
      }
    }
    return result;
  }
}

/**
 * Game of Life
 * 
 * https://leetcode.com/problems/game-of-life/
 */
public class GameOfLife {

  // Use two bits to preserve the old and new value
  public void gameOfLife(int[][] board) {
    int m = board.length, n = board[0].length;

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        int lives = liveNeighbors(board, m, n, i, j);
        // Only need to set when the 2nd bit becomes 1.
        if (board[i][j] == 1 && lives >= 2 && lives <= 3) {
          board[i][j] ^= 1 << 1; // 01 -> 11
        }
        if (board[i][j] == 0 && lives == 3) {
          board[i][j] ^= 1 << 1; // 00 -> 10
        }
      }
    }

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        board[i][j] >>= 1; // Drop the 1st bit
      }
    }
  }

  public int liveNeighbors(int[][] board, int m, int n, int i, int j) {
    int lives = 0;
    for (int x = Math.max(i - 1, 0); x <= Math.min(i + 1, m - 1); x++) {
      for (int y = Math.max(j - 1, 0); y <= Math.min(j + 1, n - 1); y++) {
        // Skip itself!
        if (x != i || y != j) {
          lives += board[x][y] & 1;
        }
      }
    }
    return lives;
  }

}

/**
 * 
 * Minimum Cost For Tickets
 * 
 * You have planned some train traveling one year in advance. The days of the year in which you will
 * travel are given as an integer array days. Each day is an integer from 1 to 365.
 * 
 * Train tickets are sold in three different ways:
 * 
 * a 1-day pass is sold for costs[0] dollars, a 7-day pass is sold for costs[1] dollars, and a
 * 30-day pass is sold for costs[2] dollars. The passes allow that many days of consecutive travel.
 * 
 * For example, if we get a 7-day pass on day 2, then we can travel for 7 days: 2, 3, 4, 5, 6, 7,
 * and 8. Return the minimum number of dollars you need to travel every day in the given list of
 * days.
 * 
 * <pre>
 * Example 1:
 *
 * Input: days = [1,4,6,7,8,20], costs = [2,7,15]
 * Output: 11
 * Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
 * On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
 * On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
 * On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
 * In total, you spent $11 and covered all the days of your travel.
 * </pre>
 * 
 * 
 * https://leetcode.com/problems/minimum-cost-for-tickets/
 *
 */
public class MinimumCostForTickets {
  public int mincostTickets(int[] days, int[] costs) {
    int[] durations = { 1, 7, 30 }; // 3 different ways
    return recursiveDP(days, costs, durations, 0, new int[days.length]);
  }

  public int recursiveDP(int[] days, int[] costs, int[] durations, int i, int[] memo) {
    if (i >= days.length) {
      return 0;
    }

    if (memo[i] != 0) {
      return memo[i];
    }

    int ans = Integer.MAX_VALUE, j = i;
    for (int d = 0; d < durations.length; d++) {
      while (j < days.length && days[j] < days[i] + durations[d]) {
        j++;
      }
      ans = Math.min(ans, recursiveDP(days, costs, durations, j, memo) + costs[d]);
    }

    memo[i] = ans;
    return ans;
  }
}

public int decodeColumnId(String colId) {
  int result = 0;
  for (int i = 0; i < colId.length(); i++) {
    result = result * 26 + (colId.charAt(i) - 'A' + 1);
  }
  return result;
}

  public void reverseWords(char[] str) {
    reverse(str, 0, str.length - 1);
    int start = 0, end = 0;
    while (end < str.length) {
      if (str[end] == ' ') {
        reverse(str, start, end - 1);
        start = end + 1;
      }
      end++;
    }
    reverse(str, start, end - 1);
  }

  private void reverse(char[] str, int start, int end) {
    while (start < end) {
      char tmp = str[start];
      str[start] = str[end];
      str[end] = tmp;
      start++;
      end--;
    }
  }

// Recursion with memoization
public boolean wordBreak1(String s, List<String> wordDict) {
  return wordBreak1(s, new HashSet<String>(wordDict), 0, new Boolean[s.length()]);
}

public boolean wordBreak1(String s, Set<String> wordDict, int start, Boolean[] memo) {
  if (start == s.length())
    return true;
  if (memo[start] != null)
    return memo[start];
  for (int end = start + 1; end <= s.length(); end++) {
    if (wordDict.contains(s.substring(start, end)) && wordBreak1(s, wordDict, end, memo))
      return memo[start] = true;
  }
  return memo[start] = false;
}

// Use Breadth-First-Search
public boolean wordBreak2(String s, List<String> wordDict) {
  Set<String> wordDictSet = new HashSet<>(wordDict);
  Queue<Integer> queue = new LinkedList<>();
  int[] visited = new int[s.length()];
  queue.add(0);

  while (!queue.isEmpty()) {
    int start = queue.remove();
    if (visited[start] == 0) {
      for (int end = start + 1; end <= s.length(); end++) {
        if (wordDictSet.contains(s.substring(start, end))) {
          queue.add(end);
          if (end == s.length())
            return true;
        }
      }
      visited[start] = 1;
    }
  }

  return false;
}

// Dynamic programming
public boolean wordBreak3(String s, List<String> wordDict) {
  Set<String> wordDictSet = new HashSet<>(wordDict);
  boolean[] found = new boolean[s.length() + 1];
  found[0] = true;
  for (int i = 1; i <= s.length(); i++) {
    for (int j = 0; j < i; j++) {
      if (found[j] && wordDictSet.contains(s.substring(j, i))) {
        found[i] = true;
        break;
      }
    }
  }
  return found[s.length()];
}

// Also can apply Trie Tree (or TST) to break earlier (if there were many words to check)

// Can also resolve the question: Concatenated Words
// A word can only be formed by words shorter than it. So we can first sort the input
// by length of each word, and only try to form one word by using words in front of it.
public List<String> findAllConcatenateWords(String[] words) {
  List<String> result = new ArrayList<>();
  Set<String> preWords = new HashSet<>();
  Arrays.sort(words, (a, b) -> (a.length() - b.length()));
  for (String word : words) {
    if (canForm(word, preWords))
      result.add(word);
    preWords.add(word);
  }
  return result;
}
private static boolean canForm(String word, Set<String> dict) {
  if (dict.isEmpty())
    return false;
  boolean[] dp = new boolean[word.length() + 1];
  dp[0] = true;
  for (int i = 1; i <= word.length(); i++) {
    for (int j = 0; j < i; j++) {
      if (dp[i] && dict.contains(word.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[word.length()];
}