package array;

import java.math.BigInteger;

import java.util.;

Created by gouthamvidyapradhan on 25/07/2019

<p>For a non-negative integer X, the array-form of X is an array of its digits in left to right

order. For example, if X = 1231, then the array form is [1,2,3,1].

<p>Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

<p>Example 1:

<p>Input: A = [1,2,0,0], K = 34 Output: [1,2,3,4] Explanation: 1200 + 34 = 1234 Example 2:

<p>Input: A = [2,7,4], K = 181 Output: [4,5,5] Explanation: 274 + 181 = 455 Example 3:

<p>Input: A = [2,1,5], K = 806 Output: [1,0,2,1] Explanation: 215 + 806 = 1021 Example 4:

<p>Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1 Output: [1,0,0,0,0,0,0,0,0,0,0] Explanation:

9999999999 + 1 = 10000000000 <p>Note：

<p>1 <= A.length <= 10000 0 <= A[i] <= 9 0 <= K <= 10000 If A.length > 1, then A[0] != 0

<p>Solution: O(N) use BigInteger to add long numbers

public class AddToArrayForm {

public static void main(String[] args) {

int [] arr ={2,4,5,2};

int toadd = 24;

List<Integer> answer = addToArrayForm(arr,toadd);

System.out.println(answer);

public static List<Integer> addToArrayForm(int[] A, int K) {

StringBuilder sb = new StringBuilder();

for (int a : A) {

sb.append(a);

System.out.println("string appended to string bulder is "+sb);

BigInteger big = new BigInteger(sb.toString());

System.out.println("Here big value is"+big);

BigInteger result = big.add(BigInteger.valueOf(K));

String resultStr = result.toString();

List<Integer> list = new ArrayList<>();

for (char a : resultStr.toCharArray()) {

list.add(Integer.parseInt(String.valueOf(a)));

return list;

package array;

import java.util.;

Created by gouthamvidyapradhan on 09/10/2019 A zero-indexed array A of length N contains all

integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]],

A[A[A[i]]], ... } subjected to the rule below.

<p>Suppose the first element in S starts with the selection of element A[i] of index = i, the

next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right

before a duplicate element occurs in S.

<p>Example 1:

<p>Input: A = [5,4,0,3,1,6,2] Output: 4 Explanation: A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4]

= 1, A[5] = 6, A[6] = 2.

<p>One of the longest S[K]: S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

<p>Note:

<p>N is an integer within the range [1, 20,000]. The elements of A are all distinct. Each element

of A is an integer within the range [0, N-1].

public class ArrayNesting {

public static void main(String[] args) {

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

System.out.println(new ArrayNesting().arrayNesting(A));

}
Set<Integer> done;

int count;

public int arrayNesting(int[] nums) {

done = new HashSet<>();

int max = 0;

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

if (!done.contains(i)) {

count = 0;

dfs(i, nums);

max = Math.max(max, count);

return max;

private void dfs(int i, int[] nums) {

done.add(i);

count++;

int n = nums[i];

if (!done.contains(n)) {

dfs(n, nums);

package array;

import java.util.;

Created by gouthamvidyapradhan on 14/08/2019 Given an array of 2n integers, your task is to group

these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of

min(ai, bi) for all i from 1 to n as large as possible.

<p>Example 1: Input: [1,4,3,2]

<p>Output: 4 Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note: n is a positive integer, which is in the range of [1, 10000]. All the integers in the array

will be in the range of [-10000, 10000].

<p>Solution: O(n log n) General idea is to pair the smallest with the next smallest value inorder

to get the max sum of minimum.

public class ArrayPartitionI {

public static void main(String[] args) {

int[] A = {1, 2, 3, 4};

System.out.println(new ArrayPartitionI().arrayPairSum(A));

public int arrayPairSum(int[] nums) {

Arrays.sort(nums);

int sum = 0;

for (int i = 1; i < nums.length; i += 2) {

sum += Math.min(nums[i - 1], nums[i]);

return sum;

package array;

Created by gouthamvidyapradhan on 12/08/2017. Given an 2D board, count how many battleships are

in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may

assume the following rules:

<p>You receive a valid board, made of only battleships or empty slots. Battleships can only be

placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row,

N columns) or Nx1 (N rows, 1 column), where N can be of any size. At least one horizontal or

vertical cell separates between two battleships - there are no adjacent battleships. Example:

X..X ...X ...X In the above board there are 2 battleships. Invalid Example: ...X XXXX ...X This

is an invalid board that you will not receive - as battleships will always have a cell separating
between them.

<p>Follow up: Could you do it in one-pass, using only O(1) extra memory and without modifying the

value of the board?

<p>Solution: The below solution works in one pass using only O(1) memory. Iterate through each

cell and add one to count if and only if the current cell equals 'X' and its adjacent upper and

left cell does not contain 'X'

public class BattleshipsInABoard {

Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {

char[][] board = {{'X', '.', '.', 'X'}, {'.', '.', '.', 'X'}, {'.', '.', '.', 'X'}};

System.out.println(new BattleshipsInABoard().countBattleships(board));

public int countBattleships(char[][] board) {

int count = 0;

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

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

if (board[i][j] == 'X') {

if (i - 1 >= 0) { // check for the boundary condition

if (board[i - 1][j] == 'X') continue;

if (j - 1 >= 0) {

if (board[i][j - 1] == 'X') {

continue;

count++;

}
}

return count;

package array;

Created by gouthamvidyapradhan on 10/03/2019 A group of two or more people wants to meet and

minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks

the home of someone in the group. The distance is calculated using Manhattan Distance, where

distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

<p>Example:

<p>Input:

<p>1 - 0 - 0 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0

<p>Output: 6

<p>Explanation: Given three people living at (0,0), (0,4), and (2,2): The point (0,2) is an ideal

meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

<p>Solution: O(N ^ 2 + M ^ 2) + O(N x M): Calculate the total number of persons in each row and

each column and then take a minimum of cartesian product of each row and each column.

public class BestMeetingPoint {

Main method

@param args

public static void main(String[] args) {

int[][] grid = {{1, 0, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}};

System.out.println(new BestMeetingPoint().minTotalDistance(grid));

public int minTotalDistance(int[][] grid) {

int[] countR = new int[grid.length];

int[] countC = new int[grid[0].length];

int[] distR = new int[grid.length];

int[] distC = new int[grid[0].length];

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

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

if (grid[i][j] == 1) {

countR[i]++;

countC[j]++;

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

for (int j = 0; j < distR.length; j++) {

if (countR[j] != 0) {

distR[i] += Math.abs(j - i) countR[j];

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

for (int j = 0; j < distC.length; j++) {

if (countC[j] != 0) {

distC[i] += Math.abs(j - i) countC[j];

int min = Integer.MAX_VALUE;

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

for (int j = 0; j < distC.length; j++) {

min = Math.min(min, distR[i] + distC[j]);

}

return min;

package array;

Created by gouthamvidyapradhan on 10/06/2017. Accepted

<p>Suppose you have a long flowerbed in which some of the plots are planted and some are not.

However, flowers cannot be planted in adjacent plots - they would compete for water and both

would die.

<p>Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means

not empty), and a number n, return if n new flowers can be planted in it without violating the

no-adjacent-flowers rule.

<p>Example 1: Input: flowerbed = [1,0,0,0,1], n = 1 Output: True Example 2: Input: flowerbed =

[1,0,0,0,1], n = 2 Output: False Note: The input array won't violate no-adjacent-flowers rule.

The input array size is in the range of [1, 20000]. n is a non-negative integer which won't

exceed the input array size.

public class CanPlaceFlowers {

Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {

int[] n = {1, 0, 0, 0, 1};

System.out.println(new CanPlaceFlowers().canPlaceFlowers(n, 1));

}
public boolean canPlaceFlowers(int[] flowerbed, int n) {

int[] T = new int[flowerbed.length + 4];

for (int i = 0, j = 2; i < flowerbed.length; i++) T[j++] = flowerbed[i];

T[0] = 1;

T[T.length - 1] = 1;

int total = 0, count = 0;

for (int i = 1; i < T.length; i++) {

if (T[i] == 0) count++;

else {

if ((count % 2) == 0) total += ((count / 2) - 1);

else total += (count / 2);

count = 0; // reset

return (total >= n);

package array;

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

Created by gouthamvidyapradhan on 04/05/2018.

<p>On a table are N cards, with a positive integer printed on the front and back of each card

(possibly different).

<p>We flip any number of cards, and after we choose one card.

<p>If the number X on the back of the chosen card is not on the front of any card, then this

number X is good.
<p>What is the smallest number that is good? If no number is good, output 0.

<p>Here, fronts[i] and backs[i] represent the number on the front and back of card i.

<p>A flip swaps the front and back numbers, so the value on the front is now on the back and vice

versa.

<p>Example:

<p>Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3] Output: 2 Explanation: If we flip the second

card, the fronts are [1,3,4,4,7] and the backs are [1,2,4,1,3]. We choose the second card, which

has number 2 on the back, and it isn't on the front of any card, so 2 is good.

<p>Note:

<p>1 <= fronts.length == backs.length <= 1000. 1 <= fronts[i] <= 2000. 1 <= backs[i] <= 2000.

public class CardFilipGame {

public static void main(String[] args) {}

public int flipgame(int[] fronts, int[] backs) {

List<Integer> numbers = new ArrayList<>();

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

numbers.add(fronts[i]);

numbers.add(backs[i]);

Collections.sort(numbers);

for (int n : numbers) {

boolean success = true;

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

if (n == fronts[i] && n == backs[i]) {

success = false;

break;

}
}

if (success) {

return n;

return 0;

package array;

Created by gouthamvidyapradhan on 28/03/2019 We stack glasses in a pyramid, where the first row

has 1 glass, the second row has 2 glasses, and so on until the 100th row. Each glass holds one

cup (250ml) of champagne.

<p>Then, some champagne is poured in the first glass at the top. When the top most glass is full,

any excess liquid poured will fall equally to the glass immediately to the left and right of it.

When those glasses become full, any excess champagne will fall equally to the left and right of

those glasses, and so on. (A glass at the bottom row has it's excess champagne fall on the

floor.)

<p>For example, after one cup of champagne is poured, the top most glass is full. After two cups

of champagne are poured, the two glasses on the second row are half full. After three cups of

champagne are poured, those two cups become full - there are 3 full glasses total now. After four

cups of champagne are poured, the third row has the middle glass half full, and the two outside

glasses are a quarter full, as pictured below.

<p>Now after pouring some non-negative integer cups of champagne, return how full the j-th glass

in the i-th row is (both i and j are 0 indexed.)

<p>Example 1: Input: poured = 1, query_glass = 1, query_row = 1 Output: 0.0 Explanation: We

poured 1 cup of champange to the top glass of the tower (which is indexed as (0, 0)). There will

be no excess liquid so all the glasses under the top glass will remain empty.
<p>Example 2: Input: poured = 2, query_glass = 1, query_row = 1 Output: 0.5 Explanation: We

poured 2 cups of champange to the top glass of the tower (which is indexed as (0, 0)). There is

one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share

the excess liquid equally, and each will get half cup of champange.

<p>Note:

<p>poured will be in the range of [0, 10 ^ 9]. query_glass and query_row will be in the range of

[0, 99].

<p>Solution: Calculate for every glass and for each row at a time. Use the value from the

previous row to calculate the current value.

@see PascalsTriangle

public class ChampagneTower {

Main method

@param args

public static void main(String[] args) {

System.out.println(new ChampagneTower().champagneTower(4, 2, 1));

public double champagneTower(int poured, int query_row, int query_glass) {

double[][] A = new double[query_row + 1][query_row + 1];

A[0][0] = poured;

for (int i = 1; i <= query_row; i++) {

for (int j = 0; j <= query_row; j++) {

if (A[i - 1][j] > 1.0) {

A[i][j] += (A[i - 1][j] - 1.0) / 2;

if (j == 0) continue;
if (A[i - 1][j - 1] > 1.0) {

A[i][j] += (A[i - 1][j - 1] - 1.0) / 2;

if (A[query_row][query_glass] > 1.0) return 1;

else return A[query_row][query_glass];

package array;

import java.util.ArrayList;

import java.util.List;

Created by gouthamvidyapradhan on 08/03/2019 We are given a list schedule of employees, which

represents the working time for each employee.

<p>Each employee has a list of non-overlapping Intervals, and these intervals are in sorted

order.

<p>Return the list of finite intervals representing common, positive-length free time for all

employees, also in sorted order.

<p>Example 1: Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] Output: [[3,4]] Explanation:

There are a total of three employees, and all common free time intervals would be [-inf, 1], [3,

4], [10, inf]. We discard any intervals that contain inf as they aren't finite. Example 2: Input:

schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]] (Even though we are

representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays.

For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not

defined.)

<p>Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.
<p>Note:

<p>schedule and schedule[i] are lists with lengths in range [1, 50]. 0 <= schedule[i].start <

schedule[i].end <= 10^8.

<p>Solution: O(L X N x N) Where L is the number of schedules, N is the length of schedules for

each employee. Merge all the intervals to form a single merged array, now by using this array

form a result array with the intervals which form the free time.

public class EmployeeFreeTime {

public static class Interval {

int start;

int end;

Interval() {

start = 0;

end = 0;

Interval(int s, int e) {

start = s;

end = e;

Main method

@param args

public static void main(String[] args) {

List<List<Interval>> schedule = new ArrayList<>();

List<Interval> ints1 = new ArrayList<>();

ints1.add(new Interval(45, 56));

ints1.add(new Interval(89, 96));

List<Interval> ints3 = new ArrayList<>();

ints3.add(new Interval(5, 21));

ints3.add(new Interval(57, 74));

schedule.add(ints1);

schedule.add(ints3);

List<Interval> result = new EmployeeFreeTime().employeeFreeTime(schedule);

for (Interval i : result) {

System.out.println(i.start + " " + i.end);

public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {

if (schedule.isEmpty()) return new ArrayList<>();

List<Interval> merged = schedule.get(0);

for (int i = 1, l = schedule.size(); i < l; i++) {

List<Interval> employeeInt = schedule.get(i);

for (Interval in : employeeInt) {

merged = merge(merged, in);

List<Interval> result = new ArrayList<>();

for (int i = 0, l = merged.size(); i + 1 < l; i++) {

if (merged.get(i).end != merged.get(i + 1).start) {

result.add(new Interval(merged.get(i).end, merged.get(i + 1).start));

return result;

private List<Interval> merge(List<Interval> list, Interval interval) {

List<Interval> result = new ArrayList<>();

for (int i = 0, l = list.size(); i < l; i++) {

Interval curr = list.get(i);

if (interval.start >= curr.start && interval.end <= curr.end) {

return list;

} else if (interval.start >= curr.start && interval.start <= curr.end) {

interval = new Interval(curr.start, interval.end);

} else if (interval.end >= curr.start && interval.end <= curr.end) {

interval = new Interval(interval.start, curr.end);

} else if (interval.end < curr.start) {

result.add(interval);

for (int j = i; j < l; j++) {

result.add(list.get(j));

return result;

} else if (interval.start > curr.end) {

result.add(curr);

result.add(interval);

return result;

package array;

import java.util.;

Created by gouthamvidyapradhan on 06/08/2019 Given an array of integers nums, write a method that

returns the "pivot" index of this array.

<p>We define the pivot index as the index where the sum of the numbers to the left of the index

is equal to the sum of the numbers to the right of the index.

<p>If no such index exists, we should return -1. If there are multiple pivot indexes, you should

return the left-most pivot index.

<p>Example 1:

<p>Input: nums = [1, 7, 3, 6, 5, 6] Output: 3 Explanation: The sum of the numbers to the left of

index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3. Also, 3 is the
first index where this occurs.

<p>Example 2:

<p>Input: nums = [1, 2, 3] Output: -1 Explanation: There is no index that satisfies the

conditions in the problem statement.

<p>Note:

<p>The length of nums will be in the range [0, 10000]. Each element nums[i] will be an integer in

the range [-1000, 1000].

<p>Solution: O(N) maintain a prefix and posfix sum array and then use this to arrive at the

answer.

public class FindPivotIndex {

public static void main(String[] args) {}

public int pivotIndex(int[] nums) {

if (nums.length == 1) return 0;

int[] left = new int[nums.length];

int[] right = new int[nums.length];

left[0] = nums[0];

for (int i = 1; i < nums.length; i++) {

left[i] = left[i - 1] + nums[i];

right[nums.length - 1] = nums[nums.length - 1];

for (int i = nums.length - 2; i >= 0; i--) {

right[i] = right[i + 1] + nums[i];

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

int l, r;

if (i == 0) {

l = 0;
} else {

l = left[i - 1];

if (i == nums.length - 1) {

r = 0;

} else {

r = right[i + 1];

if (l == r) return i;

return -1;

package array;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Map;

import java.util.Set;

Created by gouthamvidyapradhan on 25/11/2017.

<p>Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may

exist one celebrity. The definition of a celebrity is that all the other n - 1 people know

him/her but he/she does not know any of them.

<p>Now you want to find out who the celebrity is or verify that there is not one. The only thing

you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of

whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as

few questions as possible (in the asymptotic sense).

<p>You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement

a function int findCelebrity(n), your function should minimize the number of calls to knows.
<p>Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's

label if there is a celebrity in the party. If there is no celebrity, return -1.

public class FindTheCelebrity {

private static Map<Integer, Set<Integer>> map = new HashMap<>();

Main method

@param args

public static void main(String[] args) {

// initialize relationship

map.put(0, new HashSet<>());

map.put(1, new HashSet<>());

map.put(2, new HashSet<>());

map.put(3, new HashSet<>());

map.put(4, new HashSet<>());

map.put(5, new HashSet<>());

map.put(6, new HashSet<>());

map.get(0).add(3);

map.get(0).add(1);

map.get(0).add(2);

map.get(0).add(4);

map.get(0).add(5);

map.get(0).add(6);

map.get(1).add(0);

map.get(1).add(3);

map.get(1).add(2);

map.get(2).add(1);

map.get(2).add(3);

map.get(2).add(4);

map.get(4).add(2);

map.get(4).add(3);
map.get(4).add(5);

map.get(5).add(4);

map.get(5).add(3);

map.get(5).add(6);

map.get(6).add(5);

map.get(6).add(3);

map.get(6).add(0);

System.out.println(new FindTheCelebrity().findCelebrity(0));

Find celebrity

@param n

@return

public int findCelebrity(int n) {

int candidate = -1, i = 0, next = 1;

while (i < n) {

if (next >= n) break;

if (knows(i, next) && !knows(next, i)) {

i = next;

next = i + 1;

} else if ((!knows(i, next) && !knows(next, i)) || (knows(i, next) && knows(next, i))) {

i = next + 1;

next = i + 1;

} else {

next++;

candidate = i;

if (candidate == -1 || candidate >= n) return -1;

for (int j = 0; j < candidate; j++) {

if (!knows(j, candidate) || knows(candidate, j)) {

candidate = -1;
break;

return candidate;

private boolean knows(int a, int b) {

return map.get(a).contains(b);

package array;

Created by gouthamvidyapradhan on 24/06/2017. Given an unsorted integer array, find the first

missing positive integer.

<p>For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.

<p>Your algorithm should run in O(n) time and uses constant space.

public class FirstMissingPositive {

private int L;

public static void main(String[] args) throws Exception {

int[] nums = {1, 3, 5, 9};

System.out.println(new FirstMissingPositive().firstMissingPositive(nums));

public int firstMissingPositive(int[] nums) {

L = nums.length;

for (int i = 0; i < L; i++) {

if (nums[i] > 0 && nums[i] <= L && nums[i] != i + 1) {

int v = nums[i];

nums[i] = -1;

replace(v, nums);

}
}

for (int i = 0; i < L; i++) {

if (nums[i] != i + 1) return i + 1;

return L + 1;

private void replace(int i, int[] nums) {

if (i > 0 && i <= L && i != nums[i - 1]) {

int v = nums[i - 1];

nums[i - 1] = i;

replace(v, nums);

package array;

import java.util.Stack;

Created by gouthamvidyapradhan on 02/03/2019 In a row of trees, the i-th tree produces fruit with

type tree[i].

<p>You start at any tree of your choice, then repeatedly perform the following steps:

<p>Add one piece of fruit from this tree to your baskets. If you cannot, stop. Move to the next

tree to the right of the current tree. If there is no tree to the right, stop. Note that you do

not have any choice after the initial choice of starting tree: you must perform step 1, then step

2, then back to step 1, then step 2, and so on until you stop.

<p>You have two baskets, and each basket can carry any quantity of fruit, but you want each

basket to only carry one type of fruit each.

<p>What is the total amount of fruit you can collect with this procedure?
<p>Example 1:

<p>Input: [1,2,1] Output: 3 Explanation: We can collect [1,2,1]. Example 2:

<p>Input: [0,1,2,2] Output: 3 Explanation: We can collect [1,2,2]. If we started at the first

tree, we would only collect [0, 1]. Example 3:

<p>Input: [1,2,3,2,2] Output: 4 Explanation: We can collect [2,3,2,2]. If we started at the first

tree, we would only collect [1, 2]. Example 4:

<p>Input: [3,3,3,1,2,1,1,2,3,3,4] Output: 5 Explanation: We can collect [1,2,1,1,2]. If we

started at the first tree or the eighth tree, we would only collect 4 fruits.

<p>Note:

<p>1 <= tree.length <= 40000 0 <= tree[i] < tree.length

public class FruitIntoBaskets {

private int count = 0;

private int max = 0;

Main method

@param args

public static void main(String[] args) {

int[] trees = {1, 0, 3, 4, 3};

System.out.println(new FruitIntoBaskets().totalFruit(trees));

public int totalFruit(int[] tree) {

int t1 = -1, t2 = -1;

Stack<Integer> stack = new Stack<>();

for (int i : tree) {

if (i == t1 || i == t2) {
countAndMax(stack, i);

} else {

if (t1 == -1) {

t1 = i;

countAndMax(stack, i);

} else if (t2 == -1) {

t2 = i;

countAndMax(stack, i);

} else {

Stack<Integer> temp = new Stack<>();

count = 0;

t1 = stack.pop();

countAndMax(temp, t1);

while (!stack.isEmpty() && stack.peek() == t1) {

countAndMax(temp, stack.pop());

t2 = i;

stack = temp;

countAndMax(stack, i);

return max;

private void countAndMax(Stack<Integer> stack, int i) {

count++;

stack.push(i);

max = Math.max(max, count);

package array;

/
Created by gouthamvidyapradhan on 12/12/2017. Given an array of citations (each citation is a

non-negative integer) of a researcher, write a function to compute the researcher's h-index.

<p>According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her

N papers have at least h citations each, and the other N − h papers have no more than h cita ons

each."

<p>For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in

total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher

has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations

each, his h-index is 3.

<p>Note: If there are several possible values for h, the maximum one is taken as the h-index.

<p>Solution O(n) Replace all the citations which are greater than n with n, the result will not

change with this operation. Maintain a count array with count of each citations. Sum up all the

counts from n -> 0 and store this in a array S. Value in array index Si is number of papers

having citations at least i.

<p>The first value at index i, from right to left in array S which has i <= Si is the answer.

public class HIndex {

public static void main(String[] args) throws Exception {

int[] A = {3, 0, 6, 1, 5};

System.out.println(new HIndex().hIndex(A));

public int hIndex(int[] citations) {

int n = citations.length;

int[] count = new int[n + 1];

int[] S = new int[n + 1];

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

if (citations[i] > n) {

citations[i] = n;
}

for (int citation : citations) {

count[citation]++;

S[n] = count[n];

for (int i = n - 1; i >= 0; i--) {

S[i] = count[i] + S[i + 1];

for (int i = n; i >= 0; i--) {

if (i <= S[i]) {

return i;

return 0;

package array;

Created by gouthamvidyapradhan on 17/02/2018. Given a 2D integer matrix M representing the gray

scale of an image, you need to design a smoother to make the gray scale of each cell becomes the

average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has less

than 8 surrounding cells, then use as many as you can.

<p>Example 1: Input: [[1,1,1], [1,0,1], [1,1,1]] Output: [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

Explanation: For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0 For the point

(0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0 For the point (1,1): floor(8/9) =

floor(0.88888889) = 0 Note: The value in the given matrix is in the range of [0, 255]. The length

and width of the given matrix are in the range of [1, 150].

public class ImageSmoother {

int[] R = {1, -1, 0, 0, 1, -1, 1, -1};

int[] C = {0, 0, -1, 1, 1, 1, -1, -1};

public static void main(String[] args) throws Exception {}

public int[][] imageSmoother(int[][] M) {

int[][] result = new int[M.length][M[0].length];

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

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

int numCount = 0;

int totalCount = 1;

for (int k = 0; k < 8; k++) {

int newR = i + R[k];

int newC = j + C[k];

if (newR >= 0 && newC >= 0 && newR < M.length && newC < M[0].length) {

if (M[newR][newC] > 0) {

numCount += M[newR][newC];

totalCount++;

if (M[i][j] == 1) numCount++;

result[i][j] = numCount / totalCount;

return result;

package array;

import java.util.Arrays;

Created by gouthamvidyapradhan on 17/12/2017. Given an unsorted array return whether an

increasing subsequence of length 3 exists or not in the array.

<p>Formally the function should: Return true if there exists i, j, k such that arr[i] < arr[j] <
arr[k] given 0 ≤ i < j < k ≤ n-1 else return false. Your algorithm should run in O(n) time

complexity and O(1) space complexity.

<p>Examples: Given [1, 2, 3, 4, 5], return true.

<p>Given [5, 4, 3, 2, 1], return false.

public class IncreasingTripletSubsequence {

Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {

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

System.out.println(new IncreasingTripletSubsequence().increasingTriplet(A));

public boolean increasingTriplet(int[] nums) {

int[] A = new int[3];

Arrays.fill(A, Integer.MAX_VALUE);

for (int num : nums) {

if (num < A[0]) {

A[0] = num;

} else if (num < A[1] && num > A[0]) {

A[1] = num;

} else if (num < A[2] && num > A[1]) {

return true;

return false;

}
package array;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

Created by gouthamvidyapradhan on 15/12/2017. Given a set of non-overlapping intervals, insert a

new interval into the intervals (merge if necessary).

<p>You may assume that the intervals were initially sorted according to their start times.

<p>Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

<p>Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as

[1,2],[3,10],[12,16].

<p>This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

<p>Solution: O(n): Iterate through each interval and check for each overlapping case

public class InsertInterval {

public static class Interval {

int start;

int end;

Interval() {

start = 0;

end = 0;

Interval(int s, int e) {

start = s;

end = e;

/
Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {

Interval i1 = new Interval(1, 2);

Interval i2 = new Interval(3, 5);

Interval i3 = new Interval(6, 7);

Interval i4 = new Interval(8, 10);

Interval i5 = new Interval(12, 16);

List<Interval> list = Arrays.asList(i1, i2, i3, i4, i5);

List<Interval> result = new InsertInterval().insert(list, new Interval(2, 5));

result.stream().map(x -> x.start + " " + x.end).forEach(System.out::println);

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {

List<Interval> result = new ArrayList<>();

for (int i = 0, l = intervals.size(); i < l; i++) {

Interval curr = intervals.get(i);

if (newInterval.start >= curr.start && newInterval.end <= curr.end) {

insertRest(intervals, result, i);

return result; // easy case

} else if (newInterval.start < curr.start && newInterval.end > curr.end) {

newInterval = new Interval(newInterval.start, newInterval.end);

// merge and continue

} else if (newInterval.start >= curr.start

&& newInterval.start <= curr.end

&& newInterval.end > curr.end) {

newInterval = new Interval(curr.start, newInterval.end);

// merge and continue

} else if (newInterval.start < curr.start

&& newInterval.end >= curr.start

&& newInterval.end <= curr.end) {

Interval newI = new Interval(newInterval.start, curr.end);

result.add(newI);

insertRest(intervals, result, i + 1);

return result;

} else if (newInterval.start > curr.end) {

result.add(curr);

} else {

result.add(newInterval);

insertRest(intervals, result, i);

return result;

result.add(newInterval);

return result;

private void insertRest(List<Interval> intervals, List<Interval> result, int i) {

int l = intervals.size();

while (i < l) {

result.add(intervals.get(i));

i++;

package array;

import java.util.TreeSet;

Created by gouthamvidyapradhan on 01/01/2018. There is a garden with N slots. In each slot, there

is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly

one flower blooming and it will be in the status of blooming since then.

<p>Given an array flowers consists of number from 1 to N. Each number in the array represents the

place where the flower will open in that day.

<p>For example, flowers[i] = x means that the unique flower that blooms at day i will be at

position x, where i and x will be in the range from 1 to N.

<p>Also given an integer k, you need to output in which day there exists two flowers in the

status of blooming, and also the number of flowers between them is k and these flowers are not

blooming.

<p>If there isn't such day, output -1.

<p>Example 1: Input: flowers: [1,3,2] k: 1 Output: 2 Explanation: In the second day, the first

and the third flower have become blooming. Example 2: Input: flowers: [1,2,3] k: 1 Output: -1

Note: The given array will be in the range [1, 20000].

<p>Solution: O(n log n). Maintain a tree-set of bloomed flowers and for every element in the

array find the upper and lower bound bloomed flowers and calculate their difference with the

current. If the difference is k return the current day, if none found then return -1

public class KEmptySlots {

Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {

int[] A = {1, 3, 2};

System.out.println(new KEmptySlots().kEmptySlots(A, 2));

public int kEmptySlots(int[] flowers, int k) {

TreeSet<Integer> set = new TreeSet<>();

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

Integer lowerBound = set.floor(flowers[i]);

Integer upperBound = set.ceiling(flowers[i]);

if (lowerBound != null) {
if ((Math.abs(flowers[i] - lowerBound) + 1) == k) {

return i + 1;

if (upperBound != null) {

if ((Math.abs(flowers[i] - upperBound) + 1) == k) {

return i + 1;

set.add(flowers[i]);

return -1;

package array;

Created by gouthamvidyapradhan on 09/02/2018. In a given integer array nums, there is always

exactly one largest element.

<p>Find whether the largest element in the array is at least twice as much as every other number

in the array.

<p>If it is, return the index of the largest element, otherwise return -1.

<p>Example 1:

<p>Input: nums = [3, 6, 1, 0] Output: 1 Explanation: 6 is the largest integer, and for every

other number in the array x, 6 is more than twice as big as x. The index of value 6 is 1, so we

return 1.

<p>Example 2:
<p>Input: nums = [1, 2, 3, 4] Output: -1 Explanation: 4 isn't at least as big as twice the value

of 3, so we return -1.

<p>Note:

<p>nums will have a length in the range [1, 50]. Every nums[i] will be an integer in the range

[0, 99].

public class LargestNumberAtLeastTwice {

Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {}

public int dominantIndex(int[] nums) {

int index = 0, max = Integer.MIN_VALUE;

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

if (nums[i] > max) {

max = nums[i];

index = i;

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

if (i == index) continue;

if (((long) nums[i] 2) > max) {

return -1;

return index;

}
package array;

Created by gouthamvidyapradhan on 06/08/2019 Given an array of 4 digits, return the largest 24

hour time that can be made.

<p>The smallest 24 hour time is 00:00, and the largest is 23:59. Starting from 00:00, a time is

larger if more time has elapsed since midnight.

<p>Return the answer as a string of length 5. If no valid time can be made, return an empty

string.

<p>Example 1:

<p>Input: [1,2,3,4] Output: "23:41" Example 2:

<p>Input: [5,5,5,5] Output: ""

<p>Note:

<p>A.length == 4 0 <= A[i] <= 9 Solution O(N ^ 4) Check all combinations of time possible and

return the maximum possible as the answer.

public class LargestTimeForGivenDigits {

public static void main(String[] args) {

int[] A = {2, 0, 6, 6};

System.out.println(new LargestTimeForGivenDigits().largestTimeFromDigits(A));

public String largestTimeFromDigits(int[] A) {

int max = -1;

String result = "";

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

if (A[i] > 2) continue;

for (int j = 0; j < A.length; j++) {

if (j == i) continue;

if (A[i] == 2 && A[j] > 3) continue;

for (int k = 0; k < A.length; k++) {

if (k == i || k == j) continue;

if (A[k] > 5) continue;

for (int l = 0; l < A.length; l++) {

if (l == i || l == j || l == k) continue;

int value = ((A[i] 10 + A[j]) 60) + A[k] 10 + A[l];

if (value > max) {

max = value;

result = A[i] + "" + A[j] + ":" + A[k] + "" + A[l];

return result;

package array;

Created by gouthamvidyapradhan on 03/12/2017.

<p>Given an unsorted array of integers, find the length of longest continuous increasing

subsequence (subarray).

<p>Example 1: Input: [1,3,5,4,7] Output: 3 Explanation: The longest continuous increasing

subsequence is [1,3,5], its length is 3. Even though [1,3,5,7] is also an increasing subsequence,

it's not a continuous one where 5 and 7 are separated by 4. Example 2: Input: [2,2,2,2,2] Output:

1 Explanation: The longest continuous increasing subsequence is [2], its length is 1. Note:

Length of the array will not exceed 10,000.

/
public class LongestIncreasingSubsequence {

Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {

int[] A = {1, 3, 5, 4, 7};

System.out.println(new LongestIncreasingSubsequence().findLengthOfLCIS(A));

public int findLengthOfLCIS(int[] nums) {

int max = 1, count = 1;

if (nums.length == 1) return max;

if (nums.length == 0) return 0;

for (int i = 0, j = i + 1; j < nums.length; ) {

if (nums[j] > nums[i]) {

count++;

i++;

j++;

} else {

max = Math.max(max, count);

count = 0;

i = j;

j = i + 1;

return max;

package array;

Created by gouthamvidyapradhan on 14/08/2019 Given a 01 matrix M, find the longest line of

consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.

Example: Input: [[0,1,1,0], [0,1,1,0], [0,0,0,1]] Output: 3 Hint: The number of elements in the

given matrix will not exceed 10,000.

<p>Solution O(N x M) for each cell keep track of maximum value possible horizontally, vertically

and diagonally. Start iterating from left-right and top-bottom and repeat the same from

right-left and top to bottom to get max for anti-diagonal and return the max value.

public class LongestLineofConsecutiveOneinMatrix {

final int[] R = {0, 0, -1, 1};

final int[] C = {1, -1, 0, 0};

public static void main(String[] args) {

int[][] M = {

{1, 1, 0, 0, 1, 0, 0, 1, 1, 0},

{1, 0, 0, 1, 0, 1, 1, 1, 1, 1},

{1, 1, 1, 0, 0, 1, 1, 1, 1, 0},

{0, 1, 1, 1, 0, 1, 1, 1, 1, 1},

{0, 0, 1, 1, 1, 1, 1, 1, 1, 0},

{1, 1, 1, 1, 1, 1, 0, 1, 1, 1},

{0, 1, 1, 1, 1, 1, 1, 0, 0, 1},

{1, 1, 1, 1, 1, 0, 0, 1, 1, 1},

{0, 1, 0, 1, 1, 0, 1, 1, 1, 1},

{1, 1, 1, 0, 1, 0, 1, 1, 1, 1}

};

System.out.println(new LongestLineofConsecutiveOneinMatrix().longestLine(M));

class Cell {

int h, v, d;

Cell(int h, int v, int d) {

this.h = h;

this.v = v;

this.d = d;

}
}

public int longestLine(int[][] M) {

if (M.length == 0) return 0;

int max = 0;

Cell[][] cells = new Cell[M.length][M[0].length];

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

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

int h = 0, v = 0, d = 0;

if (M[i][j] == 1) {

h = 1;

v = 1;

d = 1;

max = Math.max(max, 1);

if (j - 1 >= 0) {

Cell left = cells[i][j - 1];

if (left.h > 0) {

h += left.h;

max = Math.max(max, h);

if (i - 1 >= 0) {

Cell top = cells[i - 1][j];

if (top.v > 0) {

v += top.v;

max = Math.max(max, v);

if (i - 1 >= 0 && j - 1 >= 0) {

Cell diagonal = cells[i - 1][j - 1];

if (diagonal.d > 0) {

d += diagonal.d;

max = Math.max(max, d);

}
}

cells[i][j] = new Cell(h, v, d);

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

for (int j = M[0].length - 1; j >= 0; j--) {

int h = 0, v = 0, d = 0;

if (M[i][j] == 1) {

h = 1;

v = 1;

d = 1;

max = Math.max(max, 1);

if (j + 1 < M[0].length) {

Cell left = cells[i][j + 1];

if (left.h > 0) {

h += left.h;

max = Math.max(max, h);

if (i - 1 >= 0) {

Cell top = cells[i - 1][j];

if (top.v > 0) {

v += top.v;

max = Math.max(max, v);

if (i - 1 >= 0 && j + 1 < M[0].length) {

Cell diagonal = cells[i - 1][j + 1];

if (diagonal.d > 0) {

d += diagonal.d;

max = Math.max(max, d);

}
}

cells[i][j] = new Cell(h, v, d);

return max;

package array;

import java.util.;

Created by gouthamvidyapradhan on 15/08/2019 We are given a matrix with R rows and C columns has

cells with integer coordinates (r, c), where 0 <= r < R and 0 <= c < C.

<p>Additionally, we are given a cell in that matrix with coordinates (r0, c0).

<p>Return the coordinates of all cells in the matrix, sorted by their distance from (r0, c0) from

smallest distance to largest distance. Here, the distance between two cells (r1, c1) and (r2, c2)

is the Manhattan distance, |r1 - r2| + |c1 - c2|. (You may return the answer in any order that

satisfies this condition.)

<p>Example 1:

<p>Input: R = 1, C = 2, r0 = 0, c0 = 0 Output: [[0,0],[0,1]] Explanation: The distances from (r0,

c0) to other cells are: [0,1] Example 2:

<p>Input: R = 2, C = 2, r0 = 0, c0 = 1 Output: [[0,1],[0,0],[1,1],[1,0]] Explanation: The

distances from (r0, c0) to other cells are: [0,1,1,2] The answer [[0,1],[1,1],[0,0],[1,0]] would

also be accepted as correct. Example 3:

<p>Input: R = 2, C = 3, r0 = 1, c0 = 2 Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]] Explanation:

The distances from (r0, c0) to other cells are: [0,1,1,2,2,3] There are other answers that would
also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].

<p>Note:

<p>1 <= R <= 100 1 <= C <= 100 0 <= r0 < R 0 <= c0 < C

<p>Solution: O (log (R x C)) Straight forward solution, find the Manhattan distance from the

given cell to all the cells in the grid and sort by min distance and return their coordinates.

public class MatrixCellsinDistanceOrder {

public static void main(String[] args) {

//

class Cell {

int max, i, j;

Cell(int max, int i, int j) {

this.max = max;

this.i = i;

this.j = j;

public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {

List<Cell> list = new ArrayList<>();

for (int i = 0; i < R; i++) {

for (int j = 0; j < C; j++) {

int sum = Math.abs(r0 - i) + Math.abs(c0 - j);

list.add(new Cell(sum, i, j));

list.sort(Comparator.comparingInt(o -> o.max));

int[][] A = new int[list.size()][2];

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

A[i][0] = list.get(i).i;
A[i][1] = list.get(i).j;

return A;

package array;

Created by gouthamvidyapradhan on 08/05/2019 Given a binary array, find the maximum number of

consecutive 1s in this array.

<p>Example 1: Input: [1,1,0,1,1,1] Output: 3 Explanation: The first two digits or the last three

digits are consecutive 1s. The maximum number of consecutive 1s is 3. Note:

<p>The input array will only contain 0 and 1. The length of input array is a positive integer and

will not exceed 10,000

public class MaxConsecutiveOnes {

public static void main(String[] args) {

//

public int findMaxConsecutiveOnes(int[] nums) {

int max = 0;

boolean flag = false;

int count = 0;

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

if (nums[i] == 1) {

if (!flag) {

flag = true;

count++;

max = Math.max(max, count);

} else {
count = 0;

flag = false;

return max;

package array;

Created by gouthamvidyapradhan on 08/05/2019 Given a binary array, find the maximum number of

consecutive 1s in this array if you can flip at most one 0.

<p>Example 1: Input: [1,0,1,1,0] Output: 4 Explanation: Flip the first zero will get the the

maximum number of consecutive 1s. After flipping, the maximum number of consecutive 1s is 4.

Note:

<p>The input array will only contain 0 and 1. The length of input array is a positive integer and

will not exceed 10,000 Follow up: What if the input numbers come in one by one as an infinite

stream? In other words, you can't store all numbers coming from the stream as it's too large to

hold in memory. Could you solve it efficiently?

<p>Solution: O(N) Maintain a left and right auxiliary array with counts of contagious 1's from

both directions. Now, iterate through the array and flip a 0 to 1 and sum up left and right

contagious sum of 1's and return the max sum as the answer

public class MaxConsecutiveOnesII {

public static void main(String[] args) {

//

public int findMaxConsecutiveOnes(int[] nums) {

int[] L = new int[nums.length];

int[] R = new int[nums.length];

boolean flag = false;

int count = 0;

int max = 0;

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

if (nums[j] == 1) {

if (!flag) {

flag = true;

count++;

L[j] = count;

} else {

count = 0;

flag = false;

L[j] = count;

max = Math.max(max, count);

flag = false;

count = 0;

for (int j = nums.length - 1; j >= 0; j--) {

if (nums[j] == 1) {

if (!flag) {

flag = true;

count++;

R[j] = count;

} else {

count = 0;

flag = false;

R[j] = count;

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

if (nums[i] == 0) {

int l = i == 0 ? 0 : L[i - 1];

int r = i == nums.length - 1 ? 0 : R[i + 1];

max = Math.max(max, l + r + 1);

return max;

package array;

import java.util.;

Created by gouthamvidyapradhan on 15/08/2019 Given an array A of non-negative integers, return

the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths L

and M. (For clarification, the L-length subarray could occur before or after the M-length

subarray.)

<p>Formally, return the largest V for which V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1]

+ ... + A[j+M-1]) and either:

<p>0 <= i < i + L - 1 < j < j + M - 1 < A.length, or 0 <= j < j + M - 1 < i < i + L - 1 <

A.length.

<p>Example 1:

<p>Input: A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2 Output: 20 Explanation: One choice of subarrays

is [9] with length 1, and [6,5] with length 2. Example 2:

<p>Input: A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2 Output: 29 Explanation: One choice of subarrays

is [3,8,1] with length 3, and [8,9] with length 2. Example 3:

<p>Input: A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3 Output: 31 Explanation: One choice of subarrays

is [5,6,0,9] with length 4, and [3,8] with length 3.

<p>Note:

<p>L >= 1 M >= 1 L + M <= A.length <= 1000 0 <= A[i] <= 1000 Solution O(N ^ 2) Find prefix sum of

array of length L and array of length M and keep track of their begin and end indices. Now,

brute-force compare pairs of prefix array sum where their indices don't overlap and return the

max possible answer.

public class MaximumSumofTwoNonOverlappingSubarrays {

public static void main(String[] args) {

int[] A = {2, 1, 5, 6, 0, 9, 5, 0, 3, 8};

System.out.println(new MaximumSumofTwoNonOverlappingSubarrays().maxSumTwoNoOverlap(A, 4, 3));

class MaxWithIndex {

int max, i, j;

MaxWithIndex(int max, int i, int j) {

this.max = max;

this.i = i;

this.j = j;

public int maxSumTwoNoOverlap(int[] A, int L, int M) {

List<MaxWithIndex> first = getMax(A, L);

List<MaxWithIndex> second = getMax(A, M);

int max = 0;

for (MaxWithIndex f : first) {

for (MaxWithIndex s : second) {

if (f.j < s.i || s.j < f.i) {

max = Math.max(max, f.max + s.max);

}
return max;

private List<MaxWithIndex> getMax(int[] A, int L) {

List<MaxWithIndex> list = new ArrayList<>();

int i = 0, j = L;

int sum = 0;

for (; i < L; i++) {

sum += A[i];

list.add(new MaxWithIndex(sum, 0, j - 1));

for (i = 1; j < A.length; i++, j++) {

sum -= A[i - 1];

sum += A[j];

list.add(new MaxWithIndex(sum, i, j));

return list;

package array;

Created by gouthamvidyapradhan on 10/12/2017. Given a non-negative integer, you could swap two

digits at most once to get the maximum valued number. Return the maximum valued number you could

get.

<p>Example 1: Input: 2736 Output: 7236 Explanation: Swap the number 2 and the number 7. Example

2: Input: 9973 Output: 9973 Explanation: No swap. Note: The given number is in the range [0, 108]

<p>Solution O(n): Create a array of digit index. Iterate through the digits starting from left

and in each iteration check if there is any digit which is greater than the current digit and

appearing after the current index, if found then swap and return the new integer.

public class MaximumSwap {

public static void main(String[] args) throws Exception {

System.out.println(new MaximumSwap().maximumSwap(2736));

public int maximumSwap(int num) {

int[] D = new int[10];

char[] A = String.valueOf(num).toCharArray();

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

D[A[i] - '0'] = i;

boolean found = false;

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

int digit = A[i] - '0';

for (int j = 9; j > digit; j--) {

if (D[j] > i) {

char temp = A[i];

A[i] = (char) (j + '0');

A[D[j]] = temp;

found = true;

break;

if (found) break;

return Integer.parseInt(String.valueOf(A));

package array;

import java.util.Arrays;

Created by gouthamvidyapradhan on 27/06/2017. Given an integer array, find three numbers whose

product is maximum and output the maximum product.

<p>Example 1: Input: [1,2,3] Output: 6 Example 2: Input: [1,2,3,4] Output: 24 Note: The length of

the given array will be in range [3,104] and all elements are in the range [-1000, 1000].

Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

public class MaxProductOfThreeNumbers {

public static void main(String[] args) {

int[] A = {1, 2, 3};

System.out.println(new MaxProductOfThreeNumbers().maximumProduct(A));

public int maximumProduct(int[] nums) {

Arrays.sort(nums);

int prod1 = nums[nums.length - 1] nums[nums.length - 2] nums[nums.length - 3];

int prod2 = nums[nums.length - 1] nums[0] nums[1];

return prod1 > prod2 ? prod1 : prod2;

package array;

import java.util.Arrays;

Created by gouthamvidyapradhan on 27/11/2017. Given an array of meeting time intervals consisting

of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all

meetings.

<p>For example, Given [[0, 30],[5, 10],[15, 20]], return false.

<p>Solution: Sort the interval based on the start interval. Then, for every interval check if the

previous interval ends before the start of the current interval.

public class MeetingRooms {

public static class Interval {

int start;

int end;
Interval() {

start = 0;

end = 0;

Interval(int s, int e) {

start = s;

end = e;

public static void main(String[] args) throws Exception {

Interval i1 = new Interval(0, 30);

Interval i2 = new Interval(5, 10);

Interval i3 = new Interval(15, 20);

Interval[] intervals = {i1, i2, i3};

System.out.println(new MeetingRooms().canAttendMeetings(intervals));

public boolean canAttendMeetings(Interval[] intervals) {

Arrays.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));

for (int i = 1; i < intervals.length; i++) {

if (intervals[i].start < intervals[i - 1].end) return false;

return true;

package array;

import java.util.;

Created by gouthamvidyapradhan on 19/11/2019 Given the availability time slots arrays slots1 and

slots2 of two people and a meeting duration duration, return the earliest time slot that works

for both of them and is of duration duration.

<p>If there is no common time slot that satisfies the requirements, return an empty array.
<p>The format of a time slot is an array of two elements [start, end] representing an inclusive

time range from start to end.

<p>It is guaranteed that no two availability slots of the same person intersect with each other.

That is, for any two time slots [start1, end1] and [start2, end2] of the same person, either

start1 > end2 or start2 > end1.

<p>Example 1:

<p>Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8 Output:

[60,68] Example 2:

<p>Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12 Output:

[]

<p>Constraints:

<p>1 <= slots1.length, slots2.length <= 10^4 slots1[i].length, slots2[i].length == 2 slots1[i][0]

< slots1[i][1] slots2[i][0] < slots2[i][1] 0 <= slots1[i][j], slots2[i][j] <= 10^9 1 <= duration

<= 10^6

public class MeetingScheduler {

public static void main(String[] args) {

int[][] slots1 = {{10, 50}, {60, 120}, {140, 210}};

int[][] slots2 = {{0, 15}, {60, 70}};

List<Integer> result = new MeetingScheduler().minAvailableDuration(slots1, slots2, 12);

System.out.println();

private class Node {

int s, e, type;

Node(int s, int e, int type) {

this.s = s;
this.e = e;

this.type = type;

public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {

PriorityQueue<Node> pq =

new PriorityQueue<>(

(o1, o2) -> {

int r = Integer.compare(o1.s, o2.s);

if (r == 0) {

return Integer.compare(o1.e, o2.e);

} else return r;

});

for (int[] s : slots1) {

pq.offer(new Node(s[0], s[1], 1));

for (int[] s : slots2) {

pq.offer(new Node(s[0], s[1], 2));

Node prev = null;

while (!pq.isEmpty()) {

Node node = pq.poll();

if (prev == null) {

prev = node;

} else {

if (prev.type != node.type) {

int s = Math.max(prev.s, node.s);

int e = Math.min(prev.e, node.e);

if ((e - s) >= duration) {

return Arrays.asList(s, s + duration);

if (node.e > prev.e) {

prev = node;

return new ArrayList<>();

package array;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.List;

Created by gouthamvidyapradhan on 13/06/2017. Given a collection of intervals, merge all

overlapping intervals.

<p>For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

<p>Solution: O(N log N) where N is the number of intervals 1. Sort the intervals based on start

index 2. Mark the first interval as the current interval 3. For every ith interval starting 1 ->

N, if the ith interval overlaps with the current interval then create a new current interval.

Else, add the current interval to result set and begin a new current interval.

public class MergeIntervals {

public static class Interval {

int start;

int end;

Interval() {

start = 0;

end = 0;

Interval(int s, int e) {
start = s;

end = e;

public static void main(String[] args) throws Exception {

Interval i1 = new Interval(1, 2);

Interval i2 = new Interval(3, 4);

Interval i3 = new Interval(5, 6);

Interval i4 = new Interval(1, 10);

List<Interval> result = new MergeIntervals().merge(Arrays.asList(i1, i2, i3, i4));

result.forEach((I) -> System.out.println(I.start + " " + I.end));

public List<Interval> merge(List<Interval> intervals) {

if (intervals.isEmpty()) return new ArrayList<>();

Collections.sort(intervals, (o1, o2) -> Integer.compare(o1.start, o2.start));

List<Interval> result = new ArrayList<>();

Interval curr = intervals.get(0);

for (int i = 1, l = intervals.size(); i < l; i++) {

Interval I = intervals.get(i);

if (I.start >= curr.start

&& I.start <= curr.end) { // check if the new interval overlaps with the current

curr.end = curr.end > I.end ? curr.end : I.end;

} else {

result.add(curr);

curr = I;

result.add(curr);

return result;

package array;
/

Created by gouthamvidyapradhan on 29/07/2017. Given two sorted integer arrays nums1 and nums2,

merge nums2 into nums1 as one sorted array.

<p>Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to

hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m

and n respectively.

public class MergeSortedArray {

public static void main(String[] args) throws Exception {

int[] A = {0};

int[] B = {1};

new MergeSortedArray().merge(A, 0, B, 1);

for (int i : A) System.out.println(i);

public void merge(int[] nums1, int m, int[] nums2, int n) {

int i = m + n - 1, j = m - 1, k = n - 1;

while (j >= 0 && k >= 0) nums1[i--] = (nums1[j] > nums2[k]) ? nums1[j--] : nums2[k--];

while (k >= 0) nums1[i--] = nums2[k--];

package array;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

Created by gouthamvidyapradhan on 11/04/2018. Suppose Andy and Doris want to choose a restaurant

for dinner, and they both have a list of favorite restaurants represented by strings.

<p>You need to help them find out their common interest with the least list index sum. If there

is a choice tie between answers, output all of them with no order requirement. You could assume
there always exists an answer.

<p>Example 1: Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at

Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] Output: ["Shogun"] Explanation: The only

restaurant they both like is "Shogun". Example 2: Input: ["Shogun", "Tapioca Express", "Burger

King", "KFC"] ["KFC", "Shogun", "Burger King"] Output: ["Shogun"] Explanation: The restaurant

they both like and have the least index sum is "Shogun" with index sum 1 (0+1). Note: The length

of both lists will be in the range of [1, 1000]. The length of strings in both lists will be in

the range of [1, 30]. The index is starting from 0 to the list length minus 1. No duplicates in

both lists.

<p>Solution:O(N) maintain index of each restaurant in a list using a HashMap, find the min sum of

indices and list all the restaurants which match the min sum of indices

public class MinimumIndexSumOfTwoLists {

Main method

@param args

public static void main(String[] args) throws Exception {

String[] A1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};

String[] A2 = {"Tapioca Express", "Shogun", "Burger King"};

String[] ans = new MinimumIndexSumOfTwoLists().findRestaurant(A1, A2);

for (String s : ans) {

System.out.println(s);

public String[] findRestaurant(String[] list1, String[] list2) {

int min = Integer.MAX_VALUE;

List<String> result = new ArrayList<>();

if (list2.length == 0) return new String[0];

Map<String, Integer> index = new HashMap<>();

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

index.put(list2[i], i);

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

String s = list1[i];

if (index.containsKey(s)) {

int sum = i + index.get(s);

min = Math.min(min, sum);

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

String s = list1[i];

if (index.containsKey(s)) {

int sum = i + index.get(s);

if (sum == min) {

result.add(s);

String[] resArr = new String[result.size()];

result.toArray(resArr);

return resArr;

package array;

import java.util.Arrays;

Created by gouthamvidyapradhan on 17/02/2018. Given a non-empty integer array, find the minimum

number of moves required to make all array elements equal, where a move is incrementing a

selected element by 1 or decrementing a selected element by 1.

<p>You may assume the array's length is at most 10,000.

<p>Example:

<p>Input: [1,2,3]

<p>Output: 2

<p>Explanation: Only two moves are needed (remember each move increments or decrements one

element):

<p>[1,2,3] => [2,2,3] => [2,2,2]

<p>Solution: O(n log n): Sort the array and find the median of the array. Use the median of array

to increment/decrement other value of array. Sum up the difference and return the answer.

public class MinimumMovesToEqualArray {

Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {

int[] A = {1, 2, 3};

System.out.println(new MinimumMovesToEqualArray().minMoves2(A));

public int minMoves2(int[] nums) {

if (nums.length == 1) return 0;

else if (nums.length == 2) return Math.abs(nums[0] - nums[1]);

Arrays.sort(nums);

int median;

if ((nums.length % 2) == 1) {

median = (nums.length / 2);

int sum = 0;

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

sum += Math.abs(nums[i] - nums[median]);

return sum;

} else {

median = (nums.length / 2) - 1;

int sum = 0;

int min;

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

sum += Math.abs(nums[i] - nums[median]);

min = sum;

sum = 0;

median = (nums.length / 2);

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

sum += Math.abs(nums[i] - nums[median]);

min = Math.min(min, sum);

return min;

package array;

import java.util.;

Created by gouthamvidyapradhan on 23/10/2019 Given a binary array data, return the minimum number

of swaps required to group all 1’s present in the array together in any place in the array.

<p>Example 1:

<p>Input: [1,0,1,0,1] Output: 1 Explanation: There are 3 ways to group all 1's together:

[1,1,1,0,0] using 1 swap. [0,1,1,1,0] using 2 swaps. [0,0,1,1,1] using 1 swap. The minimum is 1.

Example 2:
<p>Input: [0,0,0,1,0] Output: 0 Explanation: Since there is only one 1 in the array, no swaps

needed. Example 3:

<p>Input: [1,0,1,0,1,0,0,1,1,0,1] Output: 3 Explanation: One possible solution that uses 3 swaps

is [0,0,0,0,0,1,1,1,1,1,1]. Solution: O(N) All the 1s to be grouped together would mean that all

1s should occupy a small window in a array, this window could be in any part of the array - a

window with minimum number of 0s is the minimum number of swap required.

public class MinimumSwapsToGroupAll1Together {

public static void main(String[] args) {

//

public int minSwaps(int[] data) {

int one = 0;

int zero = 0;

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

if (data[i] == 1) {

one++;

} else zero++;

if (one == 0) return 0;

int window = one;

one = 0;

zero = 0;

int i = 0, j = window - 1;

for (int k = i; k <= j; k++) {

if (data[k] == 1) {

one++;

} else zero++;

i++;

j++;
int min = zero;

for (; j < data.length; i++, j++) {

if (data[j] == 0) {

zero++;

} else one++;

if (data[i - 1] == 0) {

zero--;

} else one--;

min = Math.min(min, zero);

return min;

package array;

import java.util.;

import java.util.stream.Collectors;

Created by gouthamvidyapradhan on 30/07/2019 Given a list of 24-hour clock time points in

"Hour:Minutes" format, find the minimum minutes difference between any two time points in the

list. Example 1: Input: ["23:59","00:00"] Output: 1 Note: The number of time points in the given

list is at least 2 and won't exceed 20000. The input time is legal and ranges from 00:00 to

23:59.

<p>Solution: O(N log N) convert each time value of the form hh:mm to minutes and sort the array.

For every pair (i, j) where j = i + 1 (also for the case where i = 0 and j = N - 1) check the

minute difference and return the minimum time difference as the answer.

public class MinimumTimeDifference {

public static void main(String[] args) {

List<String> list = Arrays.asList("23:59", "00:00");

System.out.println(new MinimumTimeDifference().findMinDifference(list));

}
public int findMinDifference(List<String> timePoints) {

List<Integer> timeInMinutes =

timePoints

.stream()

.map(

t -> {

String[] strings = t.split(":");

return Integer.parseInt(strings[0]) 60 + Integer.parseInt(strings[1]);

})

.sorted(Integer::compareTo)

.collect(Collectors.toList());

int min = Integer.MAX_VALUE;

for (int i = 1, l = timeInMinutes.size(); i < l; i++) {

int prev = timeInMinutes.get(i - 1);

int curr = timeInMinutes.get(i);

min = Math.min(min, curr - prev);

min = Math.min(min, ((24 60) - curr) + prev);

int prev = timeInMinutes.get(0);

int curr = timeInMinutes.get(timeInMinutes.size() - 1);

min = Math.min(min, curr - prev);

min = Math.min(min, ((24 60) - curr) + prev);

return min;

package array;

Created by gouthamvidyapradhan on 04/07/2017. Given an array containing n distinct numbers taken

from 0, 1, 2, ..., n, find the one that is missing from the array.

<p>For example, Given nums = [0, 1, 3] return 2.

<p>Note: Your algorithm should run in linear runtime complexity. Could you implement it using

only constant extra space complexity?

public class MissingNumber {

public static void main(String[] args) throws Exception {

int[] nums = {0};

System.out.println(new MissingNumber().missingNumber(nums));

public int missingNumber(int[] nums) {

int sum = 0;

int n = nums.length;

for (int num : nums) {

sum += num;

int arrSum = (((n + 1)) n) / 2;

if (arrSum == sum) return 0;

else return arrSum - sum;

package array;

import java.util.;

Created by gouthamvidyapradhan on 12/03/2019 Implement a MyCalendarThree class to store your

events. A new event can always be added.

<p>Your class will have one method, book(int start, int end). Formally, this represents a booking

on the half open interval [start, end), the range of real numbers x such that start <= x < end.

<p>A K-booking happens when K events have some non-empty intersection (ie., there is some time

that is common to all K events.)

<p>For each call to the method MyCalendar.book, return an integer K representing the largest
integer such that there exists a K-booking in the calendar.

<p>Your class will be called like this: MyCalendarThree cal = new MyCalendarThree();

MyCalendarThree.book(start, end) Example 1:

<p>MyCalendarThree(); MyCalendarThree.book(10, 20); // returns 1 MyCalendarThree.book(50, 60); //

returns 1 MyCalendarThree.book(10, 40); // returns 2 MyCalendarThree.book(5, 15); // returns 3

MyCalendarThree.book(5, 10); // returns 3 MyCalendarThree.book(25, 55); // returns 3 Explanation:

The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking. The

third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking. The

remaining events cause the maximum K-booking to be only a 3-booking. Note that the last event

locally causes a 2-booking, but the answer is still 3 because eg. [10, 20), [10, 40), and [5, 15)

are still triple booked.

public class MyCalendarThree {

private List<Node> events;

private int max;

private class Node {

int n, index;

Node(int n, int index) {

this.n = n;

this.index = index;

public int getN() {

return n;

public int getIndex() {

return index;

public MyCalendarThree() {

events = new ArrayList<>();

max = 0;
}

Main method

@param args

public static void main(String[] args) {

MyCalendarThree calendar = new MyCalendarThree();

System.out.println(calendar.book(10, 20));

System.out.println(calendar.book(50, 60));

System.out.println(calendar.book(10, 40));

System.out.println(calendar.book(5, 15));

System.out.println(calendar.book(5, 10));

System.out.println(calendar.book(25, 55));

public int book(int start, int end) {

events.add(new Node(start, 1));

events.add(new Node(end, 0));

events.sort((Comparator.comparing(Node::getN).thenComparing(Node::getIndex)));

int count = 0;

for (Node node : events) {

if (node.index == 1 && node.n >= end) {

break;

count += node.index == 1 ? 1 : -1;

if (node.getN() >= start) {

max = Math.max(max, count);

return max;

package array;
/

Created by gouthamvidyapradhan on 09/02/2018. You are given two arrays (without duplicates) nums1

and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for

nums1's elements in the corresponding places of nums2.

<p>The Next Greater Number of a number x in nums1 is the first greater number to its right in

nums2. If it does not exist, output -1 for this number.

<p>Example 1: Input: nums1 = [4,1,2], nums2 = [1,3,4,2]. Output: [-1,3,-1] Explanation: For

number 4 in the first array, you cannot find the next greater number for it in the second array,

so output -1. For number 1 in the first array, the next greater number for it in the second array

is 3. For number 2 in the first array, there is no next greater number for it in the second

array, so output -1. Example 2: Input: nums1 = [2,4], nums2 = [1,2,3,4]. Output: [3,-1]

Explanation: For number 2 in the first array, the next greater number for it in the second array

is 3. For number 4 in the first array, there is no next greater number for it in the second

array, so output -1. Note: All elements in nums1 and nums2 are unique. The length of both nums1

and nums2 would not exceed 1000.

public class NextGreaterElementI {

Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {

int[] A = {4, 1, 2};

int[] B = {1, 3, 4, 2};

int[] result = new NextGreaterElementI().nextGreaterElement(A, B);

System.out.println(result);

public int[] nextGreaterElement(int[] nums1, int[] nums2) {

int[] result = new int[nums1.length];

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

int n = nums1[i];

boolean found = false;

int nF = 0;

for (int j = 0; j < nums2.length; j++) {

if (nums2[j] == n) {

found = true;

if (found) {

if (nums2[j] > n) {

nF = nums2[j];

break;

if (found) {

result[i] = nF;

} else {

result[i] = -1;

return result;

package array;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

Created by gouthamvidyapradhan on 25/03/2017.

<p>Given an index k, return the kth row of the Pascal's triangle.

<p>For example, given k = 3, Return [1,3,3,1].

<p>Note: Could you optimize your algorithm to use only O(k) extra space?

public class PascalsTriangle {

public static void main(String[] args) throws Exception {

System.out.println(new PascalsTriangle().getRow(3));

public List<Integer> getRow(int rowIndex) {

int k = rowIndex;

if (k == 0) return Arrays.asList(1);

else if (k == 1) return Arrays.asList(1, 1);

else if (k == 2) return Arrays.asList(1, 2, 1);

List<Integer> result = new ArrayList<>();

result.add(2);

k = k - 2;

int p, c;

while (k-- > 0) {

p = 1;

int i = 0;

for (int l = result.size(); i < l; i++) {

c = result.get(i);

result.set(i, p + c);

p = c;

result.add(p + 1);

result.add(0, 1);

result.add(1);

return result;

}
package array;

Created by gouthamvidyapradhan on 03/02/2018. We are given an elevation map, heights[i]

representing the height of the terrain at that index. The width at each index is 1. After V units

of water fall at index K, how much water is at each index?

<p>Water first drops at index K and rests on top of the highest terrain or water at that index.

Then, it flows according to the following rules:

<p>If the droplet would eventually fall by moving left, then move left. Otherwise, if the droplet

would eventually fall by moving right, then move right. Otherwise, rise at it's current position.

Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in

that direction. Also, "level" means the height of the terrain plus any water in that column. We

can assume there's infinitely high terrain on the two sides out of bounds of the array. Also,

there could not be partial water being spread out evenly on more than 1 grid block - each unit of

water has to be in exactly one block.

<p>Example 1: Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3 Output: [2,2,2,3,2,2,2] Explanation:

# # # # ## # ### ######### 0123456 <- index

<p>The first drop of water lands at index K = 3:

<p># # # w # ## # ### ######### 0123456

<p>When moving left or right, the water can only move to the same level or a lower level. (By

level, we mean the total height of the terrain plus any water in that column.) Since moving left

will eventually make it fall, it moves left. (A droplet "made to fall" means go to a lower height

than it was at previously.)

<p># # # # ## w# ### ######### 0123456

<p>Since moving left will not make it fall, it stays in place. The next droplet falls:
<p># # # w # ## w# ### ######### 0123456

<p>Since the new droplet moving left will eventually make it fall, it moves left. Notice that the

droplet still preferred to move left, even though it could move right (and moving right makes it

fall quicker.)

<p># # # w # ## w# ### ######### 0123456

<p># # # # ##ww# ### ######### 0123456

<p>After those steps, the third droplet falls. Since moving left would not eventually make it

fall, it tries to move right. Since moving right would eventually make it fall, it moves right.

<p># # # w # ##ww# ### ######### 0123456

<p># # # # ##ww#w### ######### 0123456

<p>Finally, the fourth droplet falls. Since moving left would not eventually make it fall, it

tries to move right. Since moving right would not eventually make it fall, it stays in place:

<p># # # w # ##ww#w### ######### 0123456

<p>The final answer is [2,2,2,3,2,2,2]:

<p># ####### ####### 0123456 Example 2: Input: heights = [1,2,3,4], V = 2, K = 2 Output:

[2,3,3,4] Explanation: The last droplet settles at index 1, since moving further left would not

cause it to eventually fall to a lower height. Example 3: Input: heights = [3,1,3], V = 5, K = 1

Output: [4,4,4] Note:

<p>heights will have length in [1, 100] and contain integers in [0, 99]. V will be in range [0,

2000]. K will be in range [0, heights.length - 1].

<p>Solution: Check first left and then right to see if there are any lower levels, if yes then
drop the water at this point. Else maintain the drop at the start position

public class PourWater {

Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {

int[] A = {2, 1, 1, 2, 1, 2, 2};

int[] result = new PourWater().pourWater(A, 4, 3);

for (int i : result) {

System.out.print(i + " ");

public int[] pourWater(int[] heights, int V, int K) {

while (V-- > 0) {

heights[K] += 1;

int index = K;

int min = heights[K];

for (int i = K - 1; i >= 0; i--) {

if (heights[i] + 1 > min) {

break;

} else if (heights[i] + 1 < min) {

min = heights[i] + 1;

index = i;

if (index == K) {

for (int i = K + 1; i < heights.length; i++) {

if (heights[i] + 1 > min) {

break;

} else if (heights[i] + 1 < min) {

min = heights[i] + 1;

index = i;

if (index != K) {

heights[K]--;

heights[index]++;

return heights;

package array;

Created by gouthamvidyapradhan on 04/05/2017.

<p>Given an array of n integers where n > 1, nums, return an array output such that output[i] is

equal to the product of all the elements of nums except nums[i].

<p>Solve it without division and in O(n).

<p>For example, given [1,2,3,4], return [24,12,8,6].

<p>Follow up: Could you solve it with constant space complexity? (Note: The output array does not

count as extra space for the purpose of space complexity analysis.)

public class ProductOfArrayExceptSelf {

public static void main(String[] args) {

int[] nums = {1, 2, 3, 4};

int[] result = new ProductOfArrayExceptSelf().productExceptSelf(nums);

for (int r : result) System.out.print(r + " ");

}

public int[] productExceptSelf(int[] nums) {

int[] result = new int[nums.length];

for (int i = 0, temp = 1, l = nums.length; i < l; i++) {

result[i] = temp;

temp = nums[i];

for (int i = nums.length - 1, temp = 1; i >= 0; i--) {

result[i] = result[i] temp;

temp = nums[i];

return result;

package array;

Created by gouthamvidyapradhan on 09/12/2017. The API: int read4(char buf) reads 4 characters at

a time from a file.

<p>The return value is the actual number of characters read. For example, it returns 3 if there

is only 3 characters left in the file.

<p>By using the read4 API, implement the function int read(char buf, int n) that reads n

characters from the file.

<p>Note: The read function will only be called once for each test case.

public class ReadNCharacters {

Main method

@param args

/
public static void main(String[] args) {}

@param buf

@param n

@return

public int read(char[] buf, int n) {

int i = 0;

int toRead = Math.min(n, buf.length);

while (i < toRead) {

char[] temp = new char[4];

int r = read4(temp);

for (int j = 0; j < r && i < toRead; j++) {

buf[i] = temp[j];

i++;

if (r < 4) break;

return Math.min(i, toRead);

private int read4(char[] buf) {

return 1; // return fake value just to resolve compilation error

package array;

import java.util.ArrayList;

import java.util.List;

Created by gouthamvidyapradhan on 09/02/2018. Given scores of N athletes, find their relative

ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal",

"Silver Medal" and "Bronze Medal".

<p>Example 1: Input: [5, 4, 3, 2, 1] Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4",

"5"] Explanation: The first three athletes got the top three highest scores, so they got "Gold

Medal", "Silver Medal" and "Bronze Medal". For the left two athletes, you just need to output

their relative ranks according to their scores. Note: N is a positive integer and won't exceed

10,000. All the scores of athletes are guaranteed to be unique.

public class RelativeRanks {

class Position {

int score, poisition;

Position(int score, int position) {

this.score = score;

this.poisition = position;

Main method

@param args

@throws Exception

public static void main(String[] args) throws Exception {

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

String[] S = new RelativeRanks().findRelativeRanks(A);

for (String i : S) {

System.out.println(i);

public String[] findRelativeRanks(int[] nums) {

String[] S = new String[nums.length];

List<Position> list = new ArrayList<>();

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

list.add(new Position(nums[i], i));

list.sort((o1, o2) -> Integer.compare(o2.score, o1.score));

// Collections.reverse(list);

for (int i = 0; i < list.size(); i++) {

if (i == 0) {

S[list.get(i).poisition] = "Gold Medal";

} else if (i == 1) {

S[list.get(i).poisition] = "Silver Medal";

} else if (i == 2) {

S[list.get(i).poisition] = "Bronze Medal";

} else {

S[list.get(i).poisition] = String.valueOf(i + 1);

return S;

package array;

import java.util.;

Created by gouthamvidyapradhan on 05/12/2019 Given two arrays arr1 and arr2, the elements of arr2

are distinct, and all elements in arr2 are also in arr1.

<p>Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in

arr2. Elements that don't appear in arr2 should be placed at the end of arr1 in ascending order.

<p>Example 1:

<p>Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] Output: [2,2,2,1,4,3,3,9,6,7,19]

<p>Constraints:

<p>arr1.length, arr2.length <= 1000 0 <= arr1[i], arr2[i] <= 1000 Each arr2[i] is distinct. Each

arr2[i] is in arr1.
/

public class RelativeSortArray {

public static void main(String[] args) {

//

public int[] relativeSortArray(int[] arr1, int[] arr2) {

List<Integer> notPresent = new ArrayList<>();

Map<Integer, Integer> map = new HashMap<>();

Set<Integer> set = new HashSet<>();

for (int i : arr2) {

set.add(i);

for (int i : arr1) {

map.putIfAbsent(i, 0);

map.put(i, map.get(i) + 1);

List<Integer> result = new ArrayList<>();

for (int i : arr2) {

int count = map.get(i);

for (int j = 0; j < count; j++) {

result.add(i);

for (int k : map.keySet()) {

if (!set.contains(k)) {

int count = map.get(k);

for (int i = 0; i < count; i++) {

notPresent.add(k);

notPresent.sort(Comparator.comparingInt(o -> o));

result.addAll(notPresent);
int[] resA = new int[result.size()];

for (int i = 0; i < result.size(); i++) {

resA[i] = result.get(i);

return resA;

package array;

import java.util.ArrayDeque;

import java.util.Arrays;

Created by gouthamvidyapradhan on 12/08/2019 In a deck of cards, every card has a unique integer.

You can order the deck in any order you want.

<p>Initially, all the cards start face down (unrevealed) in one deck.

<p>Now, you do the following steps repeatedly, until all cards are revealed:

<p>Take the top card of the deck, reveal it, and take it out of the deck. If there are still

cards in the deck, put the next top card of the deck at the bottom of the deck. If there are

still unrevealed cards, go back to step 1. Otherwise, stop. Return an ordering of the deck that

would reveal the cards in increasing order.

<p>The first entry in the answer is considered to be the top of the deck.

<p>Example 1:

<p>Input: [17,13,11,2,3,5,7] Output: [2,13,3,11,5,17,7] Explanation: We get the deck in the order

[17,13,11,2,3,5,7] (this order doesn't matter), and reorder it. After reordering, the deck starts

as [2,13,3,11,5,17,7], where 2 is the top of the deck. We reveal 2, and move 13 to the bottom.

The deck is now [3,11,5,17,7,13]. We reveal 3, and move 11 to the bottom. The deck is now

[5,17,7,13,11]. We reveal 5, and move 17 to the bottom. The deck is now [7,13,11,17]. We reveal
7, and move 13 to the bottom. The deck is now [11,17,13]. We reveal 11, and move 17 to the

bottom. The deck is now [13,17]. We reveal 13, and move 17 to the bottom. The deck is now [17].

We reveal 17. Since all the cards revealed are in increasing order, the answer is correct.

<p>Note:

<p>1 <= A.length <= 1000 1 <= A[i] <= 10^6 A[i] != A[j] for all i != j

<p>Solution: O(N) General idea is to start from the last element and build the array of element

in the backwards order. Use a doubly-ended queue which allows you to poll from either end of a

queue.

public class RevealCardsInIncreasingOrder {

public static void main(String[] args) {

int[] A = {17, 13, 11, 2, 3, 5, 7};

int[] R = new RevealCardsInIncreasingOrder().deckRevealedIncreasing(A);

public int[] deckRevealedIncreasing(int[] deck) {

Arrays.sort(deck);

ArrayDeque<Integer> queue = new ArrayDeque<>();

for (int i = deck.length - 1; i >= 0; i--) {

queue.offer(deck[i]);

if (i == 0) break;

int temp = queue.pollFirst();

queue.offer(temp);

int[] answer = new int[deck.length];

int i = 0;

while (!queue.isEmpty()) {

answer[i++] = queue.pollLast();

return answer;

}
}

package array;
/
Created by gouthamvidyapradhan on 01/08/2017. Rotate an array of n elements to the
right by k
steps.

<p>For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to

[5,6,7,1,2,3,4].

<p>Note: Try to come up as many solutions as you can, there are at least 3
different ways to
solve this problem.

<p>Hint: Could you do it in-place with O(1) extra space? Related problem: Reverse
Words in a
String II
/
public class RotateArray {
/
Main method
@param args
@throws Exception
/
public static void main(String[] args) throws Exception {
int[] A = {1, 2, 3, 4, 5, 6};
new RotateArray().rotate(A, 2);
for (int i : A) System.out.print(i + " ");
}
public void rotate(int[] nums, int k) {
k = k % nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
private void reverse(int[] nums, int s, int e) {
for (int i = s, j = e; i < j; i++, j--) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}

package array;
/
Created by gouthamvidyapradhan on 21/03/2017. You are given an n x n 2D matrix
representing an
image.
 <p>Rotate the image by 90 degrees (clockwise).

<p>Follow up: Could you do this in-place?

/
public class RotateMatrix {
/
Main method
@param args
@throws Exception
/
public static void main(String[] args) throws Exception {
int[][] A = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
new RotateMatrix().rotate(A);
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
System.out.println(A[i][j]);
}
}
}
public void rotate(int[][] matrix) {
int lc = 0, tr = 0, rc = matrix[0].length - 1, br = matrix.length - 1;
while (tr < br) {
for (int i = lc, j = tr, k = rc, l = br;
i < rc && j < br && k > lc && l > tr;
i++, j++, k--, l--) {
int temp1 = matrix[j][rc];
matrix[j][rc] = matrix[tr][i];
int temp2 = matrix[br][k];
matrix[br][k] = temp1;
temp1 = matrix[l][lc];
matrix[l][lc] = temp2;
matrix[tr][i] = temp1;
}
lc++;
tr++;
rc--;
br--;
}
}
}
package array;
import java.util.HashSet;
import java.util.Set;
/
Created by pradhang on 3/28/2017. Given a m x n matrix, if an element is 0, set its
entire row
and column to 0. Do it in place.

<p>click to show follow up.

 <p>Follow up: Did you use extra space? A straight forward solution using O(mn)
space is probably
a bad idea. A simple improvement uses O(m + n) space, but still not the best
solution. Could you
devise a constant space solution?
/
public class SetMatrixZeroes {
/
Main method
@param args
@throws Exception
/
public static void main(String[] args) throws Exception {
int[][] matrix = {{0, 8, 7}, {9, 0, 8}, {9, 9, 0}};
new SetMatrixZeroes().setZeroes(matrix);
}
public void setZeroes(int[][] matrix) {
Set<Integer> row = new HashSet<>();
Set<Integer> col = new HashSet<>();
int m = matrix.length;
int n = matrix[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row.add(i);
col.add(j);
}
}
}
for (int r : row) {
for (int j = 0; j < n; j++) {
matrix[r][j] = 0;
}
}
for (int c : col) {
for (int i = 0; i < m; i++) {
matrix[i][c] = 0;
}
}
}
}
package array;
import java.util.;
/
Created by gouthamvidyapradhan on 20/08/2019 Given an array A of non-negative
integers, half of
the integers in A are odd, and half of the integers are even.

<p>Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is
even, i is even.
 <p>You may return any answer array that satisfies this condition.

<p>Example 1:

<p>Input: [4,2,5,7] Output: [4,5,2,7] Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5]

would also
have been accepted.

<p>Note:

<p>2 <= A.length <= 20000 A.length % 2 == 0 0 <= A[i] <= 1000 Solution: O(N)
straight forward
linear solution, keep track of odd and even indices and increment by 2 every time a
value is
added at the index.
/
public class SortArrayByParityII {
public static void main(String[] args) {
//
}
public int[] sortArrayByParityII(int[] A) {
int[] R = new int[A.length];
int i = 0, j = 1;
for (int a : A) {
if (a % 2 == 0) {
R[i] = a;
i += 2;
} else {
R[j] = a;
j += 2;
}
}
return R;
}
}
package array;
/
Created by gouthamvidyapradhan on 03/12/2017.

<p>Given two sparse matrices A and B, return the result of AB.

<p>You may assume that A's column number is equal to B's row number.

<p>Example:

<p>A = [ [ 1, 0, 0], [-1, 0, 3] ]

<p>B = [ [ 7, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 1 ] ]

<p>| 1 0 0 | | 7 0 0 | | 7 0 0 | AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 | | 0 0 1 |
 <p>Solution: Skip the rows and columns which you already know would result in zero
after
multiplication.
/
public class SparseMatrixMultiplication {
/
Main method
@param args
@throws Exception
/
public static void main(String[] args) throws Exception {
int[][] A = {{1, 0, 0, 1}};
int[][] B = {{7, 0, 0}, {0, 0, 0}, {0, 0, 1}, {0, 0, 1}};
int[][] C = new SparseMatrixMultiplication().multiply(A, B);
}
public int[][] multiply(int[][] A, int[][] B) {
boolean[] AH = new boolean[A.length]; // Metadata for matrix A
boolean[] BH = new boolean[B[0].length]; // Metadata for matrix A
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
if (A[i][j] != 0) {
AH[i] = true;
break;
}
}
}
for (int i = 0; i < B[0].length; i++) {
for (int j = 0; j < B.length; j++) {
if (B[j][i] != 0) {
BH[i] = true;
break;
}
}
}
int[][] C = new int[A.length][B[0].length];
for (int i = 0; i < C.length; i++) {
if (AH[i]) {
for (int j = 0; j < C[0].length; j++) {
if (BH[j]) {
int sum = 0;
for (int k = 0; k < A[0].length; k++) {
sum += A[i][k] B[k][j];
}
C[i][j] = sum;
}
}
}
}
return C;
}
}
package array;
import java.util.HashMap;
import java.util.Map;
/
Created by gouthamvidyapradhan on 03/01/2018. Given an array of integers and an
integer k, you
need to find the total number of continuous subarrays whose sum equals to k.

<p>Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Note: The length of the array

is in range [1,
20,000]. The range of numbers in the array is [-1000, 1000] and the range of the
integer k is
[-1e7, 1e7].

<p>Solution: O(n) Maintain a hash-map of prefix sum and its count and check for
range sum for
each element.
/
public class SubarraySumEqualsK {
/
Main method
@param args
@throws Exception
/
public static void main(String[] args) throws Exception {
int[] A = {1, 2, 1, -2, 3, -1, -1};
System.out.println(new SubarraySumEqualsK().subarraySum(A, 2));
}
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int sum = 0;
for (int i : nums) {
sum += i;
Integer count = map.get(sum);
if (count == null) {
map.put(sum, 1);
} else {
map.put(sum, count + 1);
}
}
sum = 0;
int result = 0;
for (int i : nums) {
int key = sum + k;
if (map.containsKey(key)) {
int count = map.get(key);
result += count;
}
sum += i;
if (map.containsKey(sum)) {
int count = map.get(sum);
if (count - 1 > 0) {
map.put(sum, count - 1);
} else {
map.remove(sum);
}
}
}
return result;
}
}
package array;
/
Created by gouthamvidyapradhan on 30/04/2019 On a N N grid, we place some 1 1 1
cubes.

<p>Each value v = grid[i][j] represents a tower of v cubes placed on top of grid

cell (i, j).

<p>Return the total surface area of the resulting shapes.

<p>Example 1:

<p>Input: [[2]] Output: 10 Example 2:

<p>Input: [[1,2],[3,4]] Output: 34 Example 3:

<p>Input: [[1,0],[0,2]] Output: 16 Example 4:

<p>Input: [[1,1,1],[1,0,1],[1,1,1]] Output: 32 Example 5:

<p>Input: [[2,2,2],[2,1,2],[2,2,2]] Output: 46

<p>Note:

<p>1 <= N <= 50 0 <= grid[i][j] <= 50

<p>Solution: O(N x M) For each cell, check each adjacent cell and sum the value of
(current cell
- adjacent cell) if the current cell value is greater than adjacent cell. For every
cell which
has value grater then 0, the top surface area is by default 1 therefore add one to
the sum of
each cell.
/
public class SurfaceAreaOfThreeDShapes {
private final int[] R = {0, 0, -1, 1};
private final int[] C = {1, -1, 0, 0};
/
Main method
@param args
/
 public static void main(String[] args) {
int[][] A = {{2}};
System.out.println(new SurfaceAreaOfThreeDShapes().surfaceArea(A));
}
public int surfaceArea(int[][] grid) {
int sum = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
int cell = grid[i][j];
for (int k = 0; k < 4; k++) {
int newR = i + R[k];
int newC = j + C[k];
if (newR >= 0 && newC >= 0 && newR < grid.length && newC < grid[0].length) {
int adjacent = grid[newR][newC];
if (cell > adjacent) {
sum += (cell - adjacent);
}
} else if (newR < 0 || newR >= grid.length || newC < 0 || newC >= grid[0].length) {
sum += cell;
}
}
if (cell > 0) {
sum += 2;
}
}
}
return sum;
}
}

package array;
/
Created by gouthamvidyapradhan on 25/03/2017. Given a non-empty array of integers,
return the
third maximum number in this array. If it does not exist, return the maximum
number. The time
complexity must be in O(n).

<p>Example 1: Input: [3, 2, 1]

<p>Output: 1

<p>Explanation: The third maximum is 1. Example 2: Input: [1, 2]

<p>Output: 2

<p>Explanation: The third maximum does not exist, so the maximum (2) is returned
instead. Example
3: Input: [2, 2, 3, 1]

<p>Output: 1
 <p>Explanation: Note that the third maximum here means the third maximum distinct
number. Both
numbers with value 2 are both considered as second maximum.
/
public class ThirdMaximumNumber {
/
Main method
@param args
@throws Exception
/
public static void main(String[] args) throws Exception {
int[] a = {1, 2};
System.out.println(new ThirdMaximumNumber().thirdMax(a));
}
public int thirdMax(int[] nums) {
long[] max = {Long.MIN_VALUE, Long.MIN_VALUE, Long.MIN_VALUE};
int count = 0;
for (int num : nums) {
for (int j = 0; j < 3; j++) {
if (max[j] > num) continue;
else if (max[j] == num) break;
int k = j;
long temp1, temp2;
temp1 = num;
count++;
while (k < 3) {
temp2 = max[k];
max[k] = temp1;
temp1 = temp2;
k++;
}
break;
}
}
System.out.println(Integer.MIN_VALUE);
return (count >= 3) ? (int) max[2] : (int) max[0];
}
}
package array;
/
Created by gouthamvidyapradhan on 18/03/2017. Given an array of integers that is
already sorted
in ascending order, find two numbers such that they add up to a specific target
number.

<p>The function twoSum should return indices of the two numbers such that they add
up to the
target, where index1 must be less than index2. Please note that your returned
answers (both
index1 and index2) are not zero-based.
 <p>You may assume that each input would have exactly one solution and you may not
use the same
element twice.

<p>Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

/
public class TwoSumII {
/
Main method
@param args
@throws Exception
/
public static void main(String[] args) throws Exception {
int[] nums = {2, 7, 11, 15};
int[] result = new TwoSumII().twoSum(nums, 23);
for (int i : result) System.out.println(i);
}
public int[] twoSum(int[] numbers, int target) {
int i = 0, j = numbers.length - 1;
while (i < j) {
int x = (numbers[i] + numbers[j]);
if (x == target) {
int[] result = new int[2];
result[0] = i + 1;
result[1] = j + 1;
return result;
} else if (x < target) i++;
else j--;
}
return new int[2];
}
}
package array;
/
Created by gouthamvidyapradhan on 29/03/2019 A Tic-Tac-Toe board is given as a
string array
board. Return True if and only if it is possible to reach this board position
during the course
of a valid tic-tac-toe game.

<p>The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The "
" character
represents an empty square.

<p>Here are the rules of Tic-Tac-Toe:

<p>Players take turns placing characters into empty squares (" "). The first player
always places
"X" characters, while the second player always places "O" characters. "X" and "O"
characters are
 always placed into empty squares, never filled ones. The game ends when there are 3
of the same
(non-empty) character filling any row, column, or diagonal. The game also ends if
all squares are
non-empty. No more moves can be played if the game is over. Example 1: Input: board
= ["O ", " ",
" "] Output: false Explanation: The first player always plays "X".

<p>Example 2: Input: board = ["XOX", " X ", " "] Output: false Explanation: Players
take turns
making moves.

<p>Example 3: Input: board = ["XXX", " ", "OOO"] Output: false

<p>Example 4: Input: board = ["XOX", "O O", "XOX"] Output: true Note:

<p>board is a length-3 array of strings, where each string board[i] has length 3.
Each
board[i][j] is a character in the set {" ", "X", "O"}.

<p>Solution: Do a brute-force check for each row, column and diagonals and keep
track of count of
'X' and 'O'
/
public class ValidTicTacToeState {
/
Main method
@param args
/
public static void main(String[] args) {
String[] board = {"XXX", "XOO", "OO "};
System.out.println(new ValidTicTacToeState().validTicTacToe(board));
}
public boolean validTicTacToe(String[] board) {
boolean xWon = hasWon(board, 'X');
boolean oWon = hasWon(board, 'O');
int xcount = 0, ocount = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i].charAt(j) == 'X') {
xcount++;
} else if (board[i].charAt(j) == 'O') {
ocount++;
}
}
}
if (xWon && oWon) return false;
if (xWon) {
return ((xcount - 1 == ocount));
} else if (oWon) {
return ((xcount == ocount));
} else {
return (xcount == ocount || xcount - 1 == ocount);
}
}
private boolean hasWon(String[] board, char c) {
boolean diagnol =
((board[0].charAt(0) == c && board[1].charAt(1) == c && board[2].charAt(2) == c)
|| (board[0].charAt(2) == c && board[1].charAt(1) == c && board[2].charAt(0) == c));
if (diagnol) return true;
for (int i = 0; i < 3; i++) {
if (board[i].charAt(0) == c && board[i].charAt(1) == c && board[i].charAt(2) == c)
return true;
}
for (int i = 0; i < 3; i++) {
if (board[0].charAt(i) == c && board[1].charAt(i) == c && board[2].charAt(i) == c)
return true;
}
return false;
}
}
-