# Arrays and Strings Questions (Part 2)

*Continuation of*

Just decided to create a new article because the previous one was getting too long.

# 271. Encode and Decode Strings

Design an algorithm to encode **a list of strings** to **a string**. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

`string encode(vector<string> strs) {`

// ... your code

return encoded_string;

}

Machine 2 (receiver) has the function:

`vector<string> decode(string s) {`

//... your code

return strs;

}

So Machine 1 does:

`string encoded_string = encode(strs);`

and Machine 2 does:

`vector<string> strs2 = decode(encoded_string);`

`strs2`

in Machine 2 should be the same as `strs`

in Machine 1.

Implement the `encode`

and `decode`

methods.

You are not allowed to solve the problem using any serialize methods (such as `eval`

).

**Example 1:**

`Input: dummy_input = ["Hello","World"]`

Output: ["Hello","World"]

Explanation:

Machine 1:

Codec encoder = new Codec();

String msg = encoder.encode(strs);

Machine 1 ---msg---> Machine 2

`Machine 2:`

Codec decoder = new Codec();

String[] strs = decoder.decode(msg);

**Example 2:**

`Input: dummy_input = [""]`

Output: [""]

Not sure what’s the point of this questions..but here is my solution

`public class Codec {`

Map<String, List<String>> map = new HashMap<>();

// Encodes a list of strings to a single string.

public String encode(List<String> strs) {

String result = "";

for(String s: strs){

result+=s;

}

map.put(result, strs);

return result;

}

// Decodes a single string to a list of strings.

public List<String> decode(String s) {

return map.getOrDefault(s, new LinkedList<>());

}

}

// Your Codec object will be instantiated and called as such:

// Codec codec = new Codec();

// codec.decode(codec.encode(strs));

# 443. String Compression

Given an array of characters `chars`

, compress it using the following algorithm:

Begin with an empty string `s`

. For each group of **consecutive repeating characters** in `chars`

:

- If the group’s length is
`1`

, append the character to`s`

. - Otherwise, append the character followed by the group’s length.

The compressed string `s`

**should not be returned separately**, but instead, be stored **in the input character array **

. Note that group lengths that are **chars**`10`

or longer will be split into multiple characters in `chars`

.

After you are done **modifying the input array,** return *the new length of the array*.

You must write an algorithm that uses only constant extra space.

**Example 1:**

`Input: chars = ["a","a","b","b","c","c","c"]`

Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

**Example 2:**

`Input: chars = ["a"]`

Output: Return 1, and the first character of the input array should be: ["a"]

Explanation: The only group is "a", which remains uncompressed since it's a single character.

**Example 3:**

`Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]`

Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

`class Solution {`

public int compress(char[] chars) {

int i=0;

int res=0;

while(i<chars.length){

int groupLen = 1;

while(i+groupLen < chars.length && chars[i+groupLen] == chars[i]){

groupLen++;

}

chars[res++]=chars[i];

if(groupLen>1){

for (char c : Integer.toString(groupLen).toCharArray()) {

chars[res++] = c;

}

}

i+=groupLen;

}

return res;

}

}

# 2384. Largest Palindromic Number

You are given a string `num`

consisting of digits only.

Return *the **largest palindromic** integer (in the form of a string) that can be formed using digits taken from *`num`

. It should not contain **leading zeroes**.

**Notes:**

- You do
**not**need to use all the digits of`num`

, but you must use**at least**one digit. - The digits can be reordered.

**Example 1:**

`Input: num = "444947137"`

Output: "7449447"

Explanation:

Use the digits "4449477" from "444947137" to form the palindromic integer "7449447".

It can be shown that "7449447" is the largest palindromic integer that can be formed.

**Example 2:**

`Input: num = "00009"`

Output: "9"

Explanation:

It can be shown that "9" is the largest palindromic integer that can be formed.

Note that the integer returned should not contain leading zeroes.

**Constraints:**

`1 <= num.length <= 105`

`num`

consists of digits.

`class Solution {`

public String largestPalindromic(String num) {

int[] count = new int[10];

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

count[num.charAt(i)- '0'] ++;

}

String result = "";

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

while(count[i] >= 2){

result+=i; // we only add 1 copy since we are creating LHS only

count[i]-=2;

}

}

// avoid leading zeros

while(result.length()>0 && count[0]>=2){

result+="0";

count[0]-=2;

}

// Add single digit

boolean hasSingleDigit = false;

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

if(count[i]>0){

hasSingleDigit = true;

result+=i;

break;

}

}

String copyResult = result;

if(!hasSingleDigit) {

result += copyResult.charAt(copyResult.length()-1);

}

// populate RHS based on LHS

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

result+=copyResult.charAt(i);

}

return result;

}

}

The idea is to first populate LHS of the palindrome string.

# 527. Word Abbreviation

Given an array of **distinct** strings `words`

, return *the minimal possible **abbreviations** for every word*.

The following are the rules for a string abbreviation:

- The
**initial**abbreviation for each word is: the first character, then the number of characters in between, followed by the last character. - If more than one word shares the
**same**abbreviation, then perform the following operation:

**Increase**the prefix (characters in the first part) of each of their abbreviations by`1`

.- For example, say you start with the words
`["abcdef","abndef"]`

both initially abbreviated as`"a4f"`

. Then, a sequence of operations would be`["a4f","a4f"]`

->`["ab3f","ab3f"]`

->`["abc2f","abn2f"]`

. - This operation is repeated until every abbreviation is
**unique**.

- At the end, if an abbreviation did not make a word shorter, then keep it as the original word.

**Example 1:**

`Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]`

Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

**Example 2:**

`Input: words = ["aa","aaa"]`

Output: ["aa","aaa"]

`class Solution {`

public List<String> wordsAbbreviation(List<String> words) {

Map<String, List<IndexedWord>> groups = new HashMap();

String[] ans = new String[words.size()];

int index = 0;

for(String word: words){

String ab = abbrev(word, 0);

if(!groups.containsKey(ab)){

groups.put(ab, new ArrayList());

}

groups.get(ab).add(new IndexedWord(word, index));

index++;

}

for(List<IndexedWord> group: groups.values()){

Collections.sort(group, (a, b) -> a.word.compareTo(b.word));

int[] lcp = new int[group.size()];

for(int i=1; i<group.size(); ++i){

int p = longestCommonPrefix(group.get(i-1).word, group.get(i).word);

lcp[i]=p;

lcp[i-1]=Math.max(lcp[i-1], p);

}

for(int i=0; i<group.size(); ++i){

ans[group.get(i).index] = abbrev(group.get(i).word, lcp[i]);

}

}

return Arrays.asList(ans);

}

public String abbrev(String word, int i) {

int N = word.length();

if (N - i <= 3) return word;

return word.substring(0, i+1) + (N - i - 2) + word.charAt(N-1);

}

public int longestCommonPrefix(String word1, String word2) {

int i = 0;

while (i < word1.length() && i < word2.length()

&& word1.charAt(i) == word2.charAt(i))

i++;

return i;

}

}

class IndexedWord {

String word;

int index;

IndexedWord(String w, int i) {

word = w;

index = i;

}

}

I copied this answer from the editorial…

# 2817. Minimum Absolute Difference Between Elements With Constraint

You are given a **0-indexed** integer array `nums`

and an integer `x`

.

Find the **minimum absolute difference** between two elements in the array that are at least `x`

indices apart.

In other words, find two indices `i`

and `j`

such that `abs(i - j) >= x`

and `abs(nums[i] - nums[j])`

is minimized.

Return* an integer denoting the **minimum** absolute difference between two elements that are at least* `x`

*indices apart*.

**Example 1:**

`Input: nums = [4,3,2,4], x = 2`

Output: 0

Explanation: We can select nums[0] = 4 and nums[3] = 4.

They are at least 2 indices apart, and their absolute difference is the minimum, 0.

It can be shown that 0 is the optimal answer.

**Example 2:**

`Input: nums = [5,3,2,10,15], x = 1`

Output: 1

Explanation: We can select nums[1] = 3 and nums[2] = 2.

They are at least 1 index apart, and their absolute difference is the minimum, 1.

It can be shown that 1 is the optimal answer.

**Example 3:**

`Input: nums = [1,2,3,4], x = 3`

Output: 3

Explanation: We can select nums[0] = 1 and nums[3] = 4.

They are at least 3 indices apart, and their absolute difference is the minimum, 3.

It can be shown that 3 is the optimal answer.

Leet Code Solution posted by another user

# Intuition

The problem essentially asks us to find two numbers in the array that:

- Have a minimum difference in their values.
- Their positions are at least x apart.

`Simple Case: Ignoring the Position Condition`

Without the second condition about the indices being x apart, the problem is simpler: you'd want to find two numbers in the array with the smallest difference between them. A straightforward way to achieve this would be to sort the numbers and then compare adjacent numbers to find the smallest difference. But for the current problem, sorting is not ideal because we lose the original indices of the elements.

However, to utilize this idea, we can use a TreeSet. It helps us maintain an ordered set of numbers and lets us search for the closest numbers efficiently.

`Incorporating the Index Distance Constraint`

Now, we need to incorporate the condition that the two numbers we pick should be at least x indices apart.

A neat approach is to iterate through the list of numbers backwards. As we move back, for every element, we check the difference with numbers that are x indices ahead and add them to our TreeSet. This way, our TreeSet always contains elements that are at least x indices ahead of our current element.

For every current element, we look for the nearest larger and smaller numbers present in the TreeSet (using the higher and lower methods). These will give us the smallest possible differences satisfying the conditions.

# Complexity

- Time complexity:

O( N log N ) : The iteration over the numbers is

O(N), and the TreeSet operations (add, higher, lower) are O(log N), O(logN) and O(logN) respectively. - Space complexity:

O ( N ) — We’re using a TreeSet to store up to N numbers

`class Solution {`

public int minAbsoluteDifference(List<Integer> nums, int x) {

int n = nums.size();

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

int result = Integer.MAX_VALUE;

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

int indexAhead = i+x;

set.add(nums.get(indexAhead));

int element = nums.get(i);

Integer min = set.lower(element+1);

Integer max = set.higher(element-1);

if(min != null){

result = Math.min(result, Math.abs(min-element));

}

if(max!=null){

result = Math.min(result, Math.abs(max-element));

}

}

return result;

}

}

# 311. Sparse Matrix Multiplication

Given two sparse matrices `mat1`

of size `m x k`

and `mat2`

of size `k x n`

, return the result of `mat1 x mat2`

. You may assume that multiplication is always possible.

**Example 1:**

`Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]`

Output: [[7,0,0],[-7,0,3]]

**Example 2:**

`Input: mat1 = [[0]], mat2 = [[0]]`

Output: [[0]]

`class Solution {`

public int[][] multiply(int[][] mat1, int[][] mat2) {

int[][] result = new int[mat1.length][mat2[0].length];

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

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

int[] row = mat1[i];

int[] colInRowForm = getCol(mat2, j);

int val = 0;

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

val+=row[w]*colInRowForm[w];

}

result[i][j]=val;

}

}

return result;

}

public int[] getCol(int[][] mat2, int j){

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

int r = 0;

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

result[r++]=mat2[i][j];

}

return result;

}

}

Key is to think of a formula for matrix multiplication.

# 2131. Longest Palindrome by Concatenating Two Letter Words

You are given an array of strings `words`

. Each element of `words`

consists of **two** lowercase English letters.

Create the **longest possible palindrome** by selecting some elements from `words`

and concatenating them in **any order**. Each element can be selected **at most once**.

Return *the **length** of the longest palindrome that you can create*. If it is impossible to create any palindrome, return `0`

.

A **palindrome** is a string that reads the same forward and backward.

**Example 1:**

`Input: words = ["lc","cl","gg"]`

Output: 6

Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.

Note that "clgglc" is another longest palindrome that can be created.

**Example 2:**

`Input: words = ["ab","ty","yt","lc","cl","ab"]`

Output: 8

Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.

Note that "lcyttycl" is another longest palindrome that can be created.

**Example 3:**

`Input: words = ["cc","ll","xx"]`

Output: 2

Explanation: One longest palindrome is "cc", of length 2.

Note that "ll" is another longest palindrome that can be created, and so is "xx".

`class Solution {`

public int longestPalindrome(String[] words) {

int result = 0;

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

HashSet<String> doubles = new HashSet<>(); // store elements like "aa", "bb"

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

String currReversed = reverseString(words[i]);

if(stringToCount.containsKey(currReversed) && stringToCount.get(currReversed) >0){

result += 4; // found a pair

stringToCount.put(currReversed, stringToCount.get(currReversed)-1);

} else {

stringToCount.putIfAbsent(words[i], 0);

stringToCount.put(words[i], stringToCount.get(words[i])+1);

}

if(currReversed.equals(words[i])){

doubles.add(currReversed);

}

}

// we only attempt to add doubles to the result at the end

// This is so that if words contains two of a double elment, meaning, it has

// 2 of "aa", then we want to make sure they are added above first.

// At the end here, we will just choose one of the doubles element and

// set that to be the central element of the final result...hence just add 2.

for(String d: doubles){

int count = stringToCount.get(d);

if(count == 1){

result+=2;

break;

}

}

return result;

}

public String reverseString(String str){

String result = "";

for(int i=str.length()-1; i>=0; i--){

result+=str.charAt(i);

}

return result;

}

}

# 68. Text Justification

Given an array of strings `words`

and a width `maxWidth`

, format the text such that each line has exactly `maxWidth`

characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces `' '`

when necessary so that each line has exactly `maxWidth`

characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

**Note:**

- A word is defined as a character sequence consisting of non-space characters only.
- Each word’s length is guaranteed to be greater than
`0`

and not exceed`maxWidth`

. - The input array
`words`

contains at least one word.

**Example 1:**

`Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16`

Output:

[

"This is an",

"example of text",

"justification. "

]

**Example 2:**

`Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16`

Output:

[

"What must be",

"acknowledgment ",

"shall be "

]

Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified.

Note that the second line is also left-justified because it contains only one word.

**Example 3:**

`Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20`

Output:

[

"Science is what we",

"understand well",

"enough to explain to",

"a computer. Art is",

"everything else we",

"do "

]

`class Solution {`

public List<String> fullJustify(String[] words, int maxWidth) {

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

int i = 0;

while (i < words.length) {

List<String> currentLine = getWords(i, words, maxWidth);

i += currentLine.size();

ans.add(createLine(currentLine, i, words, maxWidth));

}

return ans;

}

private List<String> getWords(int i, String[] words, int maxWidth) {

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

int currLength = 0;

while (i < words.length && currLength + words[i].length() <= maxWidth) {

currentLine.add(words[i]);

currLength += words[i].length() + 1;

i++;

}

return currentLine;

}

private String createLine(List<String> line, int i, String[] words, int maxWidth) {

int baseLength = -1;

for (String word: line) {

baseLength += word.length() + 1;

}

int extraSpaces = maxWidth - baseLength;

if (line.size() == 1 || i == words.length) {

return String.join(" ", line) + " ".repeat(extraSpaces);

}

int wordCount = line.size() - 1;

int spacesPerWord = extraSpaces / wordCount;

int needsExtraSpace = extraSpaces % wordCount;

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

line.set(j, line.get(j) + " ");

}

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

line.set(j, line.get(j) + " ".repeat(spacesPerWord));

}

// Add the default 1 space between words in a single line

return String.join(" ", line);

}

}

# 896. Monotonic Array

An array is **monotonic** if it is either monotone increasing or monotone decreasing.

An array `nums`

is monotone increasing if for all `i <= j`

, `nums[i] <= nums[j]`

. An array `nums`

is monotone decreasing if for all `i <= j`

, `nums[i] >= nums[j]`

.

Given an integer array `nums`

, return `true`

* if the given array is monotonic, or *`false`

* otherwise*.

**Example 1:**

`Input: nums = [1,2,2,3]`

Output: true

**Example 2:**

`Input: nums = [6,5,4,4]`

Output: true

**Example 3:**

`Input: nums = [1,3,2]`

Output: false

`class Solution {`

public boolean isMonotonic(int[] A) {

boolean increasing = true;

boolean decreasing = true;

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

if (A[i] > A[i+1])

increasing = false;

if (A[i] < A[i+1])

decreasing = false;

}

return increasing || decreasing;

}

}

My initial solution was overly complex. Here is one copied from the Editorial.

# 1235. Maximum Profit in Job Scheduling

We have `n`

jobs, where every job is scheduled to be done from `startTime[i]`

to `endTime[i]`

, obtaining a profit of `profit[i]`

.

You’re given the `startTime`

, `endTime`

and `profit`

arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time `X`

you will be able to start another job that starts at time `X`

.

**Example 1:**

`Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]`

Output: 120

Explanation: The subset chosen is the first and fourth job.

Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

**Example 2:**

`Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]`

Output: 150

Explanation: The subset chosen is the first, fourth and fifth job.

Profit obtained 150 = 20 + 70 + 60.

**Example 3:**

`Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]`

Output: 6

**Constraints:**

`1 <= startTime.length == endTime.length == profit.length <= 5 * 104`

`1 <= startTime[i] < endTime[i] <= 109`

`1 <= profit[i] <= 104`

**Editorial solution**

Notice that for every new job, we iterate over all of the previous job chains to find the most profitable chain that ends at or before the current job starts. This results in O(N2)O(N²)*O*(*N*2) time complexity. Can we do better?

Let’s take a moment and think about how we can optimize this approach.

There are two key observations to make:

- For each job we want to find all chains that end before the current job’s start time.
- Since the jobs are sorted according to start time if a chain does not conflict with the current job, then it will also not conflict with any future job.

The first observation tells us that we want to store the existing chains so that those with the earliest end time can be accessed efficiently. The second observation tells us that we do not need to remember chains that have ended, we only need to remember the maximum profit from any chain that has ended. These observations (accessing chains that have earlier end times and removing them from the data structure) hint that a heap is an efficient data structure to store the chains.

**Algorithm**

We will iterate over the jobs from left to right and for each job, we will **check if this job can be appended to any previous chain of jobs by popping out the chains from the heap**. Among all chains that do not conflict with the current job, we will append the current job to the chain with the highest profit. When we append the current job to the highest profit chain, we form a new chain. This job chain will then be pushed into the heap as a pair of the end time and the total profit (the current job’s profit plus maximum profit from non-conflicting chains).

However, there is a tricky part here. When we pop a job chain from the heap we don’t push it back into the heap, although this job chain can still be combined with other jobs in the future. To handle this case we introduce a variable `maxProfit`

whenever we pop a job chain from heap we compare its profit with the `maxProfit`

and update it accordingly. The reason is that the jobs are sorted and hence if we pop out a chain from the heap for the `ith`

job then it implies that this chain can be combined with any other job that comes after index `i`

. Therefore we only need to store the chain's profit. Furthermore, since it is always optimal to use the most profitable chain, we only need to keep track of the maximum profit seen so far. Formally at the time of `ith`

iteration, the value of `maxProfit`

will be the maximum profit of a set of job chains to which the `ith`

job can be appended.

- Store the
`startTime`

,`endTime`

, and`profit`

of each job in`jobs`

. - Sort the
`jobs`

according to their starting time. - Iterate over jobs from left to right, where
`i`

is the index of the current job. For each job

- While the job chain at the top of the priority queue does not conflict with the current job, pop from the priority queue.
- For each popped job chain compare its total profit with the
`maxProfit`

and update`maxProfit`

accordingly.

4. Push the pair of ending time and the combined profit (`maxProfit`

+ profit of this job) into the heap. This item represents the chain created by adding the current job to the most profitable job chain.

5. After iterating over all the jobs, compare the profit of the remaining chains in the priority queue with the `maxProfit`

. Return the value of `maxProfit`

.

`class Solution {`

public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {

List<Unit> jobs = new ArrayList<>();

int length = profit.length;

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

jobs.add(new Unit(startTime[i], endTime[i], profit[i]));

}

jobs.sort(Comparator.comparingInt(a -> a.start));

return findMaxProfits(jobs);

}

public int findMaxProfits(List<Unit> jobs){

int n = jobs.size();

int maxProfit = 0;

PriorityQueue<ArrayList<Integer>> pq = new PriorityQueue<>((a, b) -> a.get(0)-b.get(0));

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

int start = jobs.get(i).start;

int end = jobs.get(i).end;

int profit = jobs.get(i).profit;

// at each iteration we discard all chains that end before the current job starts.

// we discard all the chains that are compatible with the current job. Since all future jobs have a greater start-time, all the chains we discarded will be compatible with those future jobs too

while(!pq.isEmpty() && start >= pq.peek().get(0)){

maxProfit = Math.max(maxProfit, pq.peek().get(1));

pq.remove();

}

ArrayList<Integer> combinedJob = new ArrayList<>();

combinedJob.add(end);

combinedJob.add(profit + maxProfit);

pq.add(combinedJob);

}

while(!pq.isEmpty()){

maxProfit = Math.max(maxProfit, pq.peek().get(1));

pq.remove();

}

return maxProfit;

}

class Unit{

int start;

int end;

int profit;

public Unit(int start, int end, int profit){

this.start = start;

this.end = end;

this.profit = profit;

}

}

}

# 1861. Rotating the Box

You are given an `m x n`

matrix of characters `box`

representing a side-view of a box. Each cell of the box is one of the following:

- A stone
`'#'`

- A stationary obstacle
`'*'`

- Empty
`'.'`

The box is rotated **90 degrees clockwise**, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity **does not** affect the obstacles’ positions, and the inertia from the box’s rotation **does not **affect the stones’ horizontal positions.

It is **guaranteed** that each stone in `box`

rests on an obstacle, another stone, or the bottom of the box.

Return *an *`n x m`

* matrix representing the box after the rotation described above*.

**Example 1:**

`Input: box = [["#",".","#"]]`

Output: [["."],

["#"],

["#"]]

**Example 2:**

`Input: box = [["#",".","*","."],`

["#","#","*","."]]

Output: [["#","."],

["#","#"],

["*","*"],

[".","."]]

**Example 3:**

`Input: box = [["#","#","*",".","*","."],`

["#","#","#","*",".","."],

["#","#","#",".","#","."]]

Output: [[".","#","#"],

[".","#","#"],

["#","#","*"],

["#","*","."],

["#",".","*"],

["#",".","."]]

` class Solution {`

public char[][] rotateTheBox(char[][] box) {

int row = box.length, col = box[0].length;

char[][] res = new char[col][row];

// rotate first, then drop

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

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

res[j][i] = box[row-1-i][j];

}

}

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

for (int j = 0; j < row; j++) { // j can beincreasing or decreasing

if (res[i][j] == '#') {

int curRow = i;

while (curRow+1 < col && res[curRow+1][j] == '.') {

curRow++; // drop as long as is empty space

}

if (curRow != i) {

res[curRow][j] = '#';

res[i][j] = '.';

}

}

}

}

return res;

}

}

First rotate the box….

Then, drop each stone….starting from the bottom. The column does not matter.

# 658. Find K Closest Elements

Given a **sorted** integer array `arr`

, two integers `k`

and `x`

, return the `k`

closest integers to `x`

in the array. The result should also be sorted in ascending order.

An integer `a`

is closer to `x`

than an integer `b`

if:

`|a - x| < |b - x|`

, or`|a - x| == |b - x|`

and`a < b`

**Example 1:**

`Input: arr = [1,2,3,4,5], k = 4, x = 3`

Output: [1,2,3,4]

**Example 2:**

`Input: arr = [1,2,3,4,5], k = 4, x = -1`

Output: [1,2,3,4]

`class Solution {`

public List<Integer> findClosestElements(int[] arr, int k, int x) {

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

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

if(result.size()<k){

result.add(arr[i]);

} else{

int currentDiff = Math.abs(arr[i]-x);

int firstDiff = Math.abs(result.get(0)-x);

if(currentDiff<firstDiff){

result.remove(0);

result.add(arr[i]);

}

}

}

return result;

}

}

# 665. Non-decreasing Array

Given an array `nums`

with `n`

integers, your task is to check if it could become non-decreasing by modifying **at most one element**.

We define an array is non-decreasing if `nums[i] <= nums[i + 1]`

holds for every `i`

(**0-based**) such that (`0 <= i <= n - 2`

).

**Example 1:**

`Input: nums = [4,2,3]`

Output: true

Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

**Example 2:**

`Input: nums = [4,2,1]`

Output: false

Explanation: You cannot get a non-decreasing array by modifying at most one element.

`class Solution {`

public boolean checkPossibility(int[] nums) {

Boolean flag = false;

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

if(nums[i-1]>nums[i]){

if(flag) return false;

if(i<2 || nums[i-2] <= nums[i]){

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

}else{

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

}

flag=true;

}

}

return true;

}

}

This is quite tough.

The idea is that for each pair of numbers you are looking at, you choose to modify one of them, depending on some conditions.

# 725. Split Linked List in Parts

Given the `head`

of a singly linked list and an integer `k`

, split the linked list into `k`

consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return *an array of the *`k`

* parts*.

**Example 1:**

`Input: head = [1,2,3], k = 5`

Output: [[1],[2],[3],[],[]]

Explanation:

The first element output[0] has output[0].val = 1, output[0].next = null.

The last element output[4] is null, but its string representation as a ListNode is [].

**Example 2:**

`Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3`

Output: [[1,2,3,4],[5,6,7],[8,9,10]]

Explanation:

The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

`/**`

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode() {}

* ListNode(int val) { this.val = val; }

* ListNode(int val, ListNode next) { this.val = val; this.next = next; }

* }

*/

class Solution {

public ListNode[] splitListToParts(ListNode head, int k) {

ListNode[] result = new ListNode[k];

int count = 0;

ListNode tempHead = head;

while(tempHead != null){

tempHead = tempHead.next;

count++;

}

int groupSize = count/k;

int remainder = count%k;

System.out.println(groupSize + " " + k);

int j=0;

while(head != null){

ListNode currHead = head;

ListNode currTail = head;

// -1 because need to count number of steps

for(int i=0; i<groupSize + (j < remainder ? 1 : 0)-1; i++){

if(currTail != null) currTail = currTail.next;

}

if(currTail != null){

head = currTail.next;

currTail.next = null;

}

result[j]=currHead;

j++;

}

return result;

}

}

# 843. Guess the Word

You are given an array of unique strings `words`

where `words[i]`

is six letters long. One word of `words`

was chosen as a secret word.

You are also given the helper object `Master`

. You may call `Master.guess(word)`

where `word`

is a six-letter-long string, and it must be from `words`

. `Master.guess(word)`

returns:

`-1`

if`word`

is not from`words`

, or- an integer representing the number of exact matches (value and position) of your guess to the secret word.

There is a parameter `allowedGuesses`

for each test case where `allowedGuesses`

is the maximum number of times you can call `Master.guess(word)`

.

For each test case, you should call `Master.guess`

with the secret word without exceeding the maximum number of allowed guesses. You will get:

if you called**"Either you took too many guesses, or you did not find the secret word."**`Master.guess`

more than`allowedGuesses`

times or if you did not call`Master.guess`

with the secret word, or

if you called**"You guessed the secret word correctly."**`Master.guess`

with the secret word with the number of calls to`Master.guess`

less than or equal to`allowedGuesses`

.

The test cases are generated such that you can guess the secret word with a reasonable strategy (other than using the bruteforce method).

**Example 1:**

`Input: secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10`

Output: You guessed the secret word correctly.

Explanation:

master.guess("aaaaaa") returns -1, because "aaaaaa" is not in wordlist.

master.guess("acckzz") returns 6, because "acckzz" is secret and has all 6 matches.

master.guess("ccbazz") returns 3, because "ccbazz" has 3 matches.

master.guess("eiowzz") returns 2, because "eiowzz" has 2 matches.

master.guess("abcczz") returns 4, because "abcczz" has 4 matches.

We made 5 calls to master.guess, and one of them was the secret, so we pass the test case.

**Example 2:**

`Input: secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10`

Output: You guessed the secret word correctly.

Explanation: Since there are two words, you can guess both.

**Constraints:**

`1 <= words.length <= 100`

`words[i].length == 6`

`words[i]`

consist of lowercase English letters.- All the strings of
`wordlist`

are**unique**. `secret`

exists in`words`

.`10 <= allowedGuesses <= 30`

`// Time limit exceeded - failed last test case, but the logic is good enough`

class Solution {

public void findSecretWord(String[] words, Master master) {

for(int i=0, matches = 0; i<10 && matches != 6; i++){

String guess = words[words.length-1];

matches = master.guess(guess); // count how many matching chars

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

for(String word: words){

if(matches == getMatches(guess, word)){

candidates.add(word);// add words with the same num of matches

}

}

words = candidates.toArray(new String[0]);

}

}

private int getMatches(String word1, String word2){

int matches = 0;

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

if(word1.charAt(i) == word2.charAt(i)){

matches++;

}

}

return matches;

}

}

# Hangman guesser

You are to build a program to guess a list of words in hangman.

In hangman you are given a word of X letters in the form of blanks. Ex: 5 letter word, _ _ _ _ _.

You are also given a number of guesses (ex: 26). At each guess, you can pick a letter, if the letter is in the word it will be filled but if it is not then you will have lost a turn.

If you have used up all of the guesses then you will move onto the next word without guessing the word. We will tally the total number of guesses and correctly guessed words. We want to guess as many correct words in as few guesses

Your hangman program will be given 1000 words to guess. The words will be from length 4 to length 13.

Your hangman will also be given a dictionary of all the possible words to guess.

All words and guesses will be in lower case.

`import java.io.*;`

import java.util.*;

// Implement this!!

class WordGuesser {

ArrayList<String> originalWordDictionary;

ArrayList<String> wordDictionary;

Set<Character> guessedLetters;

public WordGuesser(ArrayList<String> wordDictionary) {

this.originalWordDictionary = wordDictionary;

this.wordDictionary = wordDictionary;

this.guessedLetters = new HashSet<>();

}

public char guessLetter(char[] wordState) {

ArrayList<String> trimmedWordDictionary = new ArrayList<>();

// TRIM DICT

this.wordDictionary.forEach((w) -> {

if(w.length() != wordState.length) return;

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

if(wordState[i]!='_' && w.charAt(i) != wordState[i]){

return;

}

}

trimmedWordDictionary.add(w);

});

// GUESS A RANDOM CHAR from trimmedword dict

// and one that is not guessed before.

// To maximise the chance that we guess a char correctly, we track

// the count that each char appears in the dictionary word

// and return the char with the most count

Map<Character, Integer> map = new HashMap<>();

Character maxC = '_';

int maxCount = 0;

for(String dict: trimmedWordDictionary){

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

if(wordState[i] == '_' && !guessedLetters.contains(dict.charAt(i))){

Character c = dict.charAt(i);

map.putIfAbsent(c, 0);

int count = map.get(c)+1;

map.put(c, count);

if(count>maxCount){

maxCount = count;

maxC = c;

}

}

}

}

guessedLetters.add(maxC);

this.wordDictionary = trimmedWordDictionary;

return maxC;

}

public void reset(){

guessedLetters.clear();

this.wordDictionary = this.originalWordDictionary;

}

}

class GameResult {

boolean guessedCorrectly;

int numGuesses;

int numDistictChars;

public GameResult(boolean guessedCorrectly, int numGuesses, int numDistictChars) {

this.guessedCorrectly = guessedCorrectly;

this.numGuesses = numGuesses;

this.numDistictChars = numDistictChars;

}

}

class ToyGame {

private String wordToGuess;

private ArrayList<String> wordList;

public ToyGame(ArrayList<String> wordList) {

this.wordList = wordList;

}

public void setWord(String word) {

this.wordToGuess = word;

}

public int getWordLength() {

return this.wordToGuess.length();

}

public ArrayList<Integer> submitLetter(char letter) {

ArrayList<Integer> positions = new ArrayList<Integer>();

for (int i = 0; i < this.getWordLength(); i++) {

if (this.wordToGuess.charAt(i) == letter) {

positions.add(i);

}

}

return positions;

}

private boolean isWordGuessed(char[] wordState) {

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

if (wordState[i] == '_') {

return false;

}

}

return true;

}

public GameResult run(WordGuesser guesser, boolean showOutput) {

if (showOutput) {

System.out.println("Running game");

}

Random r = new Random();

this.setWord(this.wordList.get(r.nextInt(this.wordList.size())));

char[] wordState = new char[this.wordToGuess.length()];

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

wordState[i] = '_';

}

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

char guess = guesser.guessLetter(wordState);

ArrayList<Integer> result = this.submitLetter(guess);

for (int j = 0; j < result.size(); j++) {

wordState[result.get(j)] = guess;

}

if (showOutput) {

System.out.printf("You guessed letter: %s\n", guess);

System.out.printf("Current word state: %s\n", new String(wordState));

}

if (this.isWordGuessed(wordState)) {

return new GameResult(true, i, (int) this.wordToGuess.chars().distinct().count());

}

}

if (showOutput) {

System.out.printf("Failed to guess word: %s\n", this.wordToGuess);

}

return new GameResult(false, 26, (int) this.wordToGuess.chars().distinct().count());

}

}

class Main {

private static ArrayList<String> WORD_DICT = new ArrayList<String>(Arrays.asList("abdominous", "alveolitis", "amimide", "amorism", "amygdala", "anacardium",

"angeline", "angiosperm", "antioxidizer", "apterium", "apyretic", "aquativeness", "araneoidea", "argyrosomus",

"arilloid", "bacillicidal", "bandeau", "belletrist", "benda", "bigarade", "biradiated", "blubberingly", "boghole",

"bookbinding", "bosthoon", "bulimia", "carburometer", "carmot", "celtish", "chenopodiales", "chiococca",

"ciceroni", "cockroach", "constabulary", "contraband", "coracomorphae", "costrel", "crinose", "curl",

"cystoscopic", "damningness", "darkskin", "deathday", "deflowerer", "delirious", "demulsify", "depolymerize",

"detruncation", "dioscorine", "disecondary", "drinker", "earnful", "electroscope", "erigenia", "evilspeaking",

"exquisitism", "finick", "fosite", "galvanism", "gamboised", "geckoid", "gorsechat", "guardianless", "gulose",

"hewel", "hogshead", "homoveratrole", "horsejockey", "hydrangeaceae", "hydrotropic", "incognizance", "indone",

"ingrained", "inmate", "invertedly", "irrelevance", "karyoschisis", "kerwham", "kobi", "laryngograph",

"lineation", "lunn", "mastigure", "mellitic", "mende", "mercurialism", "micawberism", "microgyria", "millet",

"millinering", "mischance", "misgive", "modeling", "mohel", "montepulciano", "monzonitic", "mosquitoproof",

"mugget", "myelomere", "napa", "nonlicet", "nonsequacious", "nowroze", "oclock", "odontatrophy", "overrake",

"pantostomata", "paroch", "paroptic", "particulate", "peccability", "peculiarism", "pervulgation", "phrenesis",

"pinacone", "planetlike", "planographic", "pogonion", "polymolybdate", "poppyhead", "preaccordance",

"precipitable", "precontent", "prefragrance", "prerefuse", "prismatic", "prunably", "pseudocarpous", "psychology",

"pteropodan", "puddening", "pulpal", "quadrumanous", "quickset", "realizably", "rebeget", "revere", "rewayle",

"rheostatics", "ridgepoled", "riempie", "rinneite", "rocouyenne", "roundel", "sacrospinal", "salse",

"saltatorial", "sayability", "scenarioist", "sciomantic", "scyllarus", "scythic", "semisacred", "serge",

"serpivolant", "shehitah", "sillandar", "silverfin", "slad", "smither", "snakepiece", "solecist", "sotik",

"spiculae", "stepstone", "stricker", "stroboscopic", "stubbleward", "styracin", "subnivean", "subparallel",

"subserrate", "subsist", "subversionary", "supertragical", "thuja", "tourette", "treddle", "trimestrial",

"typhosepsis", "umbrellaless", "unclassible", "uncreatedness", "unextendedly", "unfavored", "unflurried",

"ungentled", "uniocular", "unmonetary", "unpatrician", "unrefitted", "unrioted", "untainted", "valedictorily",

"veratrine", "verticomental", "vesical", "viseman", "visit", "whistlewing", "winsome", "wistlessness",

"woolstock", "zingel", "zooecia"));

public static void main(String[] args) {

WordGuesser guesser = new WordGuesser(WORD_DICT);

ToyGame toyGame = new ToyGame(WORD_DICT);

int numGames = 1000;

boolean shouldPrint = numGames == 1 ? true : false;

int totalWins = 0;

int totalGuesses = 0;

int bestPossibleScore = 0;

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

GameResult result = toyGame.run(guesser, shouldPrint);

if (result.guessedCorrectly) {

totalWins += 1;

}

totalGuesses += result.numGuesses;

bestPossibleScore += result.numDistictChars;

guesser.reset();

}

System.out.printf("In %s games you guessed %s words in %s guesses\n", numGames, totalWins, totalGuesses);

System.out.printf("Best possible score was: %s\n", bestPossibleScore);

}

}

# 1101. The Earliest Moment When Everyone Become Friends

There are n people in a social group labeled from `0`

to `n - 1`

. You are given an array `logs`

where `logs[i] = [timestampi, xi, yi]`

indicates that `xi`

and `yi`

will be friends at the time `timestampi`

.

Friendship is **symmetric**. That means if `a`

is friends with `b`

, then `b`

is friends with `a`

. Also, person `a`

is acquainted with a person `b`

if `a`

is friends with `b`

, or `a`

is a friend of someone acquainted with `b`

.

Return *the earliest time for which every person became acquainted with every other person*. If there is no such earliest time, return `-1`

.

**Example 1:**

`Input: logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], n = 6`

Output: 20190301

Explanation:

The first event occurs at timestamp = 20190101, and after 0 and 1 become friends, we have the following friendship groups [0,1], [2], [3], [4], [5].

The second event occurs at timestamp = 20190104, and after 3 and 4 become friends, we have the following friendship groups [0,1], [2], [3,4], [5].

The third event occurs at timestamp = 20190107, and after 2 and 3 become friends, we have the following friendship groups [0,1], [2,3,4], [5].

The fourth event occurs at timestamp = 20190211, and after 1 and 5 become friends, we have the following friendship groups [0,1,5], [2,3,4].

The fifth event occurs at timestamp = 20190224, and as 2 and 4 are already friends, nothing happens.

The sixth event occurs at timestamp = 20190301, and after 0 and 3 become friends, we all become friends.

**Example 2:**

`Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4`

Output: 3

Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.

`class Solution {`

public int earliestAcq(int[][] logs, int count) {

Arrays.sort(logs, (a, b) -> a[0] - b[0]);

HashMap<Integer, Integer> individualToGroup = new HashMap<>();

HashMap<Integer, Set<Integer>> groupToIndividuals = new HashMap<>();

int groupCount = count;

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

int time = logs[i][0];

int person1 = logs[i][1];

int person2 = logs[i][2];

if(individualToGroup.containsKey(person1) && individualToGroup.containsKey(person2)){

if(individualToGroup.get(person1) < individualToGroup.get(person2)){

int person2Group = individualToGroup.get(person2);

individualToGroup.put(person2, individualToGroup.get(person1));

Set<Integer> neigh = groupToIndividuals.get(person2Group);

for(int n: neigh){

individualToGroup.put(n, individualToGroup.get(person1));

groupToIndividuals.get(individualToGroup.get(person1)).add(n);

}

groupToIndividuals.remove(person2Group);

} else if(individualToGroup.get(person1) > individualToGroup.get(person2)) {

int person1Group = individualToGroup.get(person1);

individualToGroup.put(person1, individualToGroup.get(person2));

Set<Integer> neigh = groupToIndividuals.get(person1Group);

for(int n: neigh){

individualToGroup.put(n, individualToGroup.get(person2));

groupToIndividuals.get(individualToGroup.get(person2)).add(n);

}

groupToIndividuals.remove(person1Group);

}

} else if(individualToGroup.containsKey(person1)){

int person1Group = individualToGroup.get(person1);

individualToGroup.put(person2, person1Group);

groupToIndividuals.get(person1Group).add(person2);

} else if (individualToGroup.containsKey(person2)){

int person2Group = individualToGroup.get(person2);

individualToGroup.put(person1, person2Group);

groupToIndividuals.get(person2Group).add(person1);

} else {

individualToGroup.put(person1, groupCount);

individualToGroup.put(person2, groupCount);

HashSet<Integer> friends = new HashSet<>();

friends.add(person1);

friends.add(person2);

groupToIndividuals.put(groupCount, friends);

groupCount++;

}

if(groupToIndividuals.size() == 1 && individualToGroup.size()==count) return time;

}

return -1;

}

}

My general algorithm is to assign the current pair to a group (that is not used), if both of them do not have neighbours already assigned to groups.

Otherwise, just assign the smaller group number of the two items in the pair to the item with a bigger group number. Eg, if item1 has bigger group number, we assign it to the group number of item2. Then, find the neighbours of item1 and assign them to the smaller group number as well.

Keep doing this and we expect the groups to decrease until 1.

Use HashSet and HashMap to track the information.

## Leet code solution

## Approach: Union-Find (Disjoint-Set)

**Intuition**

This problem deals with the relationship or membership of entities.

For those of you who are familiar with a data structure called ** Union-Find**, this problem might ring a bell.

In fact, it is a perfect example that demonstrates the advantages of

**data structure (also known as Disjoint-Set).**

*Union-Find*

Union-Find (a.k.aDisjoint-Set) is a data structure that keeps track of theconnectivitiesamong interconnected individualsefficiently. With Union-Find, one can quickly determine which group a specific individual belongs to. In addition, one can quickly merge two individuals together along with the two groups that they belong to.

As suggested by its name, a typical Union-Find data structure usually provides two interfaces as follows:

`find(a)`

: this function returns the group that the individual`a`

belongs to.`union(a, b)`

: this function merges the two groups that the individuals`a`

and`b`

belong to respectively, if the groups are not of the same group already.

To make the `union(a, b)`

function more useful, one can return a boolean value in the function to indicate whether the merging actually happens or not.

For example, `union(a, b)`

would return true when `a`

and `b`

(and their respective groups) are merged together, and false when `a`

and `b`

are already in the same group and thus do not need to be merged together.

Now, imagine that we already have the above Union-Find data structure available, we can go over the problem again and try to come up with a solution using the data structure.

`class Solution {`

public int earliestAcq(int[][] logs, int n) {

// In order to ensure that we find the _earliest_ moment,

// first of all we need to sort the events in chronological order.

Arrays.sort(logs, new Comparator<int[]>() {

@Override

public int compare(int[] log1, int[] log2) {

Integer tsp1 = new Integer(log1[0]);

Integer tsp2 = new Integer(log2[0]);

return tsp1.compareTo(tsp2);

}

});

// Initially, we treat each individual as a separate group.

int groupCount = n;

UnionFind uf = new UnionFind(n);

for (int[] log : logs) {

int timestamp = log[0];

int friendA = log[1];

int friendB = log[2];

// We merge the groups along the way.

if (uf.union(friendA, friendB)) {

groupCount -= 1;

}

// The moment when all individuals are connected to each other.

if (groupCount == 1) {

return timestamp;

}

}

// There are still more than one groups left,

// i.e. not everyone is connected.

return -1;

}

}

** Yes, talk is cheap.** But still, here are a few more words to help you better understand the above code.

- In order to discover the
*earliest*moment, we must first ensure that we read through the logs in chronological order.

Since there is no mentioning whether the logs are ordered or not in the problem description, we need to**sort**them first. - Once the logs are
*sorted*by time, we then iterate through them, while applying the Union-Find data structure. - For each log, we connect the two individuals that were involved in the log, by applying the
`union(a, b)`

function. - Each log adds more connections among the individuals.

A connection is*useful*if the two individuals are separated (disjoint), or*redundant*if the two individuals are connected already via other individuals. - Initially, we treat each individual as a separate group. The number of groups decreases along with the
*useful*merging operations.

The moment when the number of groups is reduced to one is the*earliest*moment when everyone becomes connected (friends).

**Implementation**

In the above solutions, we assume that the Union-Find data structure has been implemented.

In this section, we provide a complete solution with an ** optimized** implementation of the Union-Find data structure.

By

*optimized*, we apply the

**path compression**optimization in the

`find(a)`

interface and **union by rank**in the

`union(a, b)`

interface.For those of you who are not familiar with the data structure, we have an Explore Card that dives into more details, including the optimization techniques mentioned here.

`class Solution {`

public int earliestAcq(int[][] logs, int n) {

// First, we need to sort the events in chronological order.

Arrays.sort(logs, new Comparator<int[]>() {

@Override

public int compare(int[] log1, int[] log2) {

Integer tsp1 = new Integer(log1[0]);

Integer tsp2 = new Integer(log2[0]);

return tsp1.compareTo(tsp2);

}

});

// Initially, we treat each individual as a separate group.

int groupCount = n;

UnionFind uf = new UnionFind(n);

for (int[] log : logs) {

int timestamp = log[0], friendA = log[1], friendB = log[2];

// We merge the groups along the way.

if (uf.union(friendA, friendB)) {

groupCount -= 1;

}

// The moment when all individuals are connected to each other.

if (groupCount == 1) {

return timestamp;

}

}

// There are still more than one groups left,

// i.e. not everyone is connected.

return -1;

}

}

class UnionFind {

private int[] group;

private int[] rank;

public UnionFind(int size) {

this.group = new int[size];

this.rank = new int[size];

for (int person = 0; person < size; ++person) {

this.group[person] = person;

this.rank[person] = 0;

}

}

/** Return the id of group that the person belongs to. */

public int find(int person) {

if (this.group[person] != person)

this.group[person] = this.find(this.group[person]);

return this.group[person];

}

/**

* If it is necessary to merge the two groups that x, y belong to.

* @return true: if the groups are merged.

*/

public boolean union(int a, int b) {

int groupA = this.find(a);

int groupB = this.find(b);

boolean isMerged = false;

// The two people share the same group.

if (groupA == groupB)

return isMerged;

// Otherwise, merge the two groups.

isMerged = true;

// Merge the lower-rank group into the higher-rank group.

if (this.rank[groupA] > this.rank[groupB]) {

this.group[groupB] = groupA;

} else if (this.rank[groupA] < this.rank[groupB]) {

this.group[groupA] = groupB;

} else {

this.group[groupA] = groupB;

this.rank[groupB] += 1;

}

return isMerged;

}

}

# 252. Meeting Rooms

Given an array of meeting time `intervals`

where `intervals[i] = [starti, endi]`

, determine if a person could attend all meetings.

**Example 1:**

`Input: intervals = [[0,30],[5,10],[15,20]]`

Output: false

**Example 2:**

`Input: intervals = [[7,10],[2,4]]`

Output: true

**Constraints:**

`0 <= intervals.length <= 104`

`intervals[i].length == 2`

`0 <= starti < endi <= 106`

`class Solution {`

public boolean canAttendMeetings(int[][] intervals) {

Arrays.sort(intervals, (a, b) -> a[0]-b[0]);

int prevEnd=0;

for(int[] i: intervals){

if(i[0] < prevEnd){

return false;

}

prevEnd = i[1];

}

return true;

}

}

# 253. Meeting Rooms II

Given an array of meeting time intervals `intervals`

where `intervals[i] = [starti, endi]`

, return *the minimum number of conference rooms required*.

**Example 1:**

`Input: intervals = [[0,30],[5,10],[15,20]]`

Output: 2

**Example 2:**

`Input: intervals = [[7,10],[2,4]]`

Output: 1

**Constraints:**

`1 <= intervals.length <= 104`

`0 <= starti < endi <= 106`

`class Solution {`

public int minMeetingRooms(int[][] intervals) {

// Check for the base case. If there are no intervals, return 0

if (intervals.length == 0) {

return 0;

}

// Min heap

PriorityQueue<Integer> allocator =

new PriorityQueue<Integer>(

intervals.length,

new Comparator<Integer>() {

public int compare(Integer a, Integer b) {

return a - b;

}

});

// Sort the intervals by start time

Arrays.sort(intervals, (a, b) -> {

if(a[0] != b[0]) return a[0]-b[0];

return a[1]-b[1];

});

// Add the first meeting

allocator.add(intervals[0][1]);

// Iterate over remaining intervals

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

// If the room due to free up the earliest is free, assign that room to this meeting.

if (intervals[i][0] >= allocator.peek()) {

allocator.poll();

}

// If a new room is to be assigned, then also we add to the heap,

// If an old room is allocated, then also we have to add to the heap with updated end time.

allocator.add(intervals[i][1]);

}

// The size of the heap tells us the minimum rooms required for all the meetings.

return allocator.size();

}

}

# 1229. Meeting Scheduler

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`

.

If there is no common time slot that satisfies the requirements, return an **empty array**.

The format of a time slot is an array of two elements `[start, end]`

representing an inclusive time range from `start`

to `end`

.

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`

.

**Example 1:**

`Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8`

Output: [60,68]

**Example 2:**

`Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12`

Output: []

**Constraints:**

`1 <= slots1.length, slots2.length <= 104`

`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] <= 109`

`1 <= duration <= 106`

`class Solution {`

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

// TODO sort

Arrays.sort(slots1, (a, b)->a[0]-b[0]);

Arrays.sort(slots2, (a, b) -> a[0]-b[0]);

/*

Overlapping scenarios

---

---

------

---

---

---

*/

int i=0;

int j=0;

while(i<slots1.length && j<slots2.length){

if(slots1[i][1]>slots2[j][0] || slots1[i][0]<slots2[j][1]){

// has overlap

List<Integer> overlap = new LinkedList<>();

overlap.add(Math.max(slots1[i][0], slots2[j][0]));

overlap.add(Math.min(slots1[i][1], slots2[j][1]));

if(overlap.get(1)-overlap.get(0) >= duration){

List<Integer> res = new LinkedList<>();

res.add(overlap.get(0));

res.add(overlap.get(0)+duration); // don't allocate more than you need

return res;

}

}

if(slots1[i][1] < slots2[j][1]){

i++; // move pointer for the slot with earlier end time

} else {

j++;

}

}

return new LinkedList<>();

}

}

# 2210. Count Hills and Valleys in an Array

You are given a **0-indexed** integer array `nums`

. An index `i`

is part of a **hill** in `nums`

if the closest non-equal neighbors of `i`

are smaller than `nums[i]`

. Similarly, an index `i`

is part of a **valley** in `nums`

if the closest non-equal neighbors of `i`

are larger than `nums[i]`

. Adjacent indices `i`

and `j`

are part of the **same** hill or valley if `nums[i] == nums[j]`

.

Note that for an index to be part of a hill or valley, it must have a non-equal neighbor on **both** the left and right of the index.

Return *the number of hills and valleys in *`nums`

.

**Example 1:**

`Input: nums = [2,4,1,1,6,5]`

Output: 3

Explanation:

At index 0: There is no non-equal neighbor of 2 on the left, so index 0 is neither a hill nor a valley.

At index 1: The closest non-equal neighbors of 4 are 2 and 1. Since 4 > 2 and 4 > 1, index 1 is a hill.

At index 2: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 2 is a valley.

At index 3: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 3 is a valley, but note that it is part of the same valley as index 2.

At index 4: The closest non-equal neighbors of 6 are 1 and 5. Since 6 > 1 and 6 > 5, index 4 is a hill.

At index 5: There is no non-equal neighbor of 5 on the right, so index 5 is neither a hill nor a valley.

There are 3 hills and valleys so we return 3.

**Example 2:**

`Input: nums = [6,6,5,5,4,1]`

Output: 0

Explanation:

At index 0: There is no non-equal neighbor of 6 on the left, so index 0 is neither a hill nor a valley.

At index 1: There is no non-equal neighbor of 6 on the left, so index 1 is neither a hill nor a valley.

At index 2: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 2 is neither a hill nor a valley.

At index 3: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 3 is neither a hill nor a valley.

At index 4: The closest non-equal neighbors of 4 are 5 and 1. Since 4 < 5 and 4 > 1, index 4 is neither a hill nor a valley.

At index 5: There is no non-equal neighbor of 1 on the right, so index 5 is neither a hill nor a valley.

There are 0 hills and valleys so we return 0.

`class Solution {`

public int countHillValley(int[] nums) {

int count = 0;

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

if(nums[i]>nums[i-1] && nums[i]>nums[i+1]){

count++;

}

if(nums[i]<nums[i-1] && nums[i]<nums[i+1]){

count++;

}

if(nums[i] == nums[i+1]){

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

}

}

return count;

}

}

# 953. Verifying an Alien Dictionary

In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different `order`

. The `order`

of the alphabet is some permutation of lowercase letters.

Given a sequence of `words`

written in the alien language, and the `order`

of the alphabet, return `true`

if and only if the given `words`

are sorted lexicographically in this alien language.

**Example 1:**

`Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"`

Output: true

Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

**Example 2:**

`Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"`

Output: false

Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

**Example 3:**

`Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"`

Output: false

Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

`class Solution {`

public boolean isAlienSorted(String[] words, String order) {

// build order hashmap

HashMap<Character, Integer> orderMap = new HashMap<>();

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

orderMap.put(order.charAt(i), i);

}

// check

for(int i=0; i<words.length-1; i++){

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

if(j >= words[i+1].length()) return false;

if(words[i].charAt(j) != words[i+1].charAt(j)){

int curr = orderMap.get(words[i].charAt(j));

int next = orderMap.get(words[i+1].charAt(j));

if(curr>next) return false;

else break;

}

}

}

return true;

}

}

# 269. Alien Dictionary

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

You are given a list of strings `words`

from the alien language's dictionary. Now it is claimed that the strings in `words`

are

**sorted lexicographically**

by the rules of this new language.

If this claim is incorrect, and the given arrangement of string in `words`

cannot correspond to any order of letters, return `"".`

Otherwise, return *a string of the unique letters in the new alien language sorted in **lexicographically increasing order** by the new language’s rules. *If there are multiple solutions, return* *** any of them**.

**Example 1:**

`Input: words = ["wrt","wrf","er","ett","rftt"]`

Output: "wertf"

**Example 2:**

`Input: words = ["z","x"]`

Output: "zx"

**Example 3:**

`Input: words = ["z","x","z"]`

Output: ""

Explanation: The order is invalid, so return "".

`class Solution {`

private Map<Character, List<Character>> reverseAdjList = new HashMap<>();

private Map<Character, Boolean> seen = new HashMap<>();

private StringBuilder output = new StringBuilder();

public String alienOrder(String[] words) {

// Step 0: Put all unique letters into reverseAdjList as keys.

for (String word : words) {

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

reverseAdjList.putIfAbsent(c, new ArrayList<>());

}

}

// Step 1: Find all edges and add reverse edges to reverseAdjList.

for (int i = 0; i < words.length - 1; i++) {

String word1 = words[i];

String word2 = words[i + 1];

// Check that word2 is not a prefix of word1.

if (word1.length() > word2.length() && word1.startsWith(word2)) {

return "";

}

// Find the first non match and insert the corresponding relation.

for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {

if (word1.charAt(j) != word2.charAt(j)) {

reverseAdjList.get(word2.charAt(j)).add(word1.charAt(j));

break;

}

}

}

System.out.println(reverseAdjList);

// Step 2: DFS to build up the output list.

for (Character c : reverseAdjList.keySet()) {

boolean result = dfs(c);

if (!result) return "";

}

return output.toString();

}

// Return true iff no cycles detected.

private boolean dfs(Character c) {

if (seen.containsKey(c)) {

return seen.get(c); // If this node was grey (false), a cycle was detected.

}

seen.put(c, false);

for (Character next : reverseAdjList.get(c)) {

boolean result = dfs(next);

if (!result) return false;

}

seen.put(c, true);

output.append(c);

return true;

}

}

If we made a reverse adjacency list instead of a forward one, the output order would be correct (without needing to be reversed). Remember that when we reverse the edges of a directed graph, the nodes with no incoming edges became the ones with no outgoing edges. This means that the ones at the start of the alphabet will now be the ones returned first.

One issue we need to be careful of is cycles. In directed graphs, we often detect cycles by using **graph coloring**. All nodes start as white, and then once they’re first visited they become grey, and then once all their outgoing nodes have been fully explored, they become black. We know there is a cycle if we *enter* a node that is currently grey (it works because all nodes that are currently on the stack are grey. Nodes are changed to black when they are removed from the stack).

# 1518. Water Bottles

There are `numBottles`

water bottles that are initially full of water. You can exchange `numExchange`

empty water bottles from the market with one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers `numBottles`

and `numExchange`

, return *the **maximum** number of water bottles you can drink*.

**Example 1:**

`Input: numBottles = 9, numExchange = 3`

Output: 13

Explanation: You can exchange 3 empty bottles to get 1 full water bottle.

Number of water bottles you can drink: 9 + 3 + 1 = 13.

**Example 2:**

`Input: numBottles = 15, numExchange = 4`

Output: 19

Explanation: You can exchange 4 empty bottles to get 1 full water bottle.

Number of water bottles you can drink: 15 + 3 + 1 = 19.

**Constraints:**

`1 <= numBottles <= 100`

`2 <= numExchange <= 100`

`class Solution {`

public int numWaterBottles(int numBottles, int numExchange) {

int count = numBottles;

int drank = numBottles;

while(count>=numExchange){

int newBottles = count/numExchange;

int remainingOldBottles = count%numExchange;

drank += newBottles;

count = newBottles + remainingOldBottles;

}

return drank;

}

}