Degree of an array
Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.
Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.
Input: nums = [1,2,2,3,1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.
Track the first, last indices and number of occurances of each number
Update the maxFrequency number as you go along, along with the number itself
If a number has same frequency as this, then choose the one that has lower distance between first and last index
Map<Integer, int[]> map = new HashMap<>(); //first index, last index, number of occurances
int maxFrequency = 0, maxFreqElement = 0;
for(int index=0; index<nums.length; index++) {
int number = nums[index];
int[] numberValue = map.getOrDefault(number, new int[]{index, index, 1});
if (index != numberValue[1]) {
numberValue[2]++;
}
numberValue[1] = index;
map.put(number, numberValue);
if (numberValue[2] > maxFrequency) {
maxFrequency = numberValue[2];
maxFreqElement = number;
} else if (numberValue[2] == maxFrequency) {
int[] maxValue = map.get(maxFreqElement);
if (numberValue[1]-numberValue[0] < maxValue[1]-maxValue[0]) {
maxFrequency = numberValue[2];
maxFreqElement = number;
}
}
}
int lastIndex = map.get(maxFreqElement)[1];
int firstIndex = map.get(maxFreqElement)[0];
return lastIndex - firstIndex + 1;Minimize Maximum Pair Sum in Array
The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.
For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.
Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:
Each element of nums is in exactly one pair, and
The maximum pair sum is minimized.
Return the minimized maximum pair sum after optimally pairing up the elements.
Input: nums = [3,5,2,3]
Output: 7
Explanation: The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.
Example 2:
Sort and add up leftmost and rightmost elements, take max of all sums
Arrays.sort(nums);
int left=0, right = nums.length-1;
int result=Integer.MIN_VALUE;
while(left<right) {
result = Math.max(result, nums[left]+nums[right]);
left++;
right--;
}
return result;Earliest Possible Day of Full Bloom
You have n flower seeds. Every seed must be planted first before it can begin to grow, then bloom. Planting a seed takes time and so does the growth of a seed. You are given two 0-indexed integer arrays plantTime and growTime, of length n each:
plantTime[i] is the number of full days it takes you to plant the ith seed. Every day, you can work on planting exactly one seed. You do not have to work on planting the same seed on consecutive days, but the planting of a seed is not complete until you have worked plantTime[i] days on planting it in total.
growTime[i] is the number of full days it takes the ith seed to grow after being completely planted. After the last day of its growth, the flower blooms and stays bloomed forever.
From the beginning of day 0, you can plant the seeds in any order.
Return the earliest possible day where all seeds are blooming.
Input: plantTime = [1,2,3,2], growTime = [2,1,2,1]
Output: 9
One optimal way is:
On day 1, plant the 0th seed. The seed grows for 2 full days and blooms on day 4.
On days 0 and 3, plant the 1st seed. The seed grows for 1 full day and blooms on day 5.
On days 2, 4, and 5, plant the 2nd seed. The seed grows for 2 full days and blooms on day 8.
On days 6 and 7, plant the 3rd seed. The seed grows for 1 full day and blooms on day 9.
Thus, on day 9, all the seeds are blooming.
Use greedy approach by planting seeds with longest growth time first.
Integer[] indicesOfSeeds = new Integer[plantTime.length];
for(int index=0; index<plantTime.length; index++)
indicesOfSeeds[index] = index;
Arrays.sort(indicesOfSeeds, (index1, index2) -> growTime[index2] - growTime[index1]);
int result = 0;
int time = 0;
for(int index: indicesOfSeeds) {
time = time + plantTime[index];
result = Math.max(result, time + growTime[index]);
}
return result;
