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 2Machine 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 tos. - 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 chars. Note that group lengths that are 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 <= 105numconsists 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
0and not exceedmaxWidth. - The input array
wordscontains 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: trueExample 2:
Input: nums = [6,5,4,4]
Output: trueExample 3:
Input: nums = [1,3,2]
Output: falseclass 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: 6Constraints:
1 <= startTime.length == endTime.length == profit.length <= 5 * 1041 <= startTime[i] < endTime[i] <= 1091 <= 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(N2) 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, andprofitof each job injobs. - Sort the
jobsaccording to their starting time. - Iterate over jobs from left to right, where
iis 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
maxProfitand updatemaxProfitaccordingly.
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|anda < 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:
-1ifwordis not fromwords, 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:
"Either you took too many guesses, or you did not find the secret word."if you calledMaster.guessmore thanallowedGuessestimes or if you did not callMaster.guesswith the secret word, or"You guessed the secret word correctly."if you calledMaster.guesswith the secret word with the number of calls toMaster.guessless than or equal toallowedGuesses.
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 <= 100words[i].length == 6words[i]consist of lowercase English letters.- All the strings of
wordlistare unique. secretexists inwords.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 Union-Find data structure (also known as Disjoint-Set).
Union-Find (a.k.a Disjoint-Set) is a data structure that keeps track of the connectivities among interconnected individuals efficiently. 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 individualabelongs to.union(a, b): this function merges the two groups that the individualsaandbbelong 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: falseExample 2:
Input: intervals = [[7,10],[2,4]]
Output: trueConstraints:
0 <= intervals.length <= 104intervals[i].length == 20 <= 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: 2Example 2:
Input: intervals = [[7,10],[2,4]]
Output: 1Constraints:
1 <= intervals.length <= 1040 <= 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 <= 104slots1[i].length, slots2[i].length == 2slots1[i][0] < slots1[i][1]slots2[i][0] < slots2[i][1]0 <= slots1[i][j], slots2[i][j] <= 1091 <= 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 <= 1002 <= 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;
}
}