I have a list of integers as input, the order of items in input is not important.
I need to form a new list having size n with the below features.
Here i, j represents the index position of the output list such that i < j < n
Items from 0 to i should be in increasing order strictly
Items from i to j should be in decreasing order strictly
Items from j to n should be in increasing order strictly
The new list must satisfy the above properties, and it need not have all the elements from the original input list.
Example 1:
input [2, 1, 3, 3, 1, 2, 1, 2, 3]
valid output sequence with max selected items is [1,2,3,2,1,2,3]
size of this output sequence is 7, so return the value 7
Explanation:
increasing from position 0 to 2 => [1,2,3]
decreasing from position 2 to 4 => [3,2,1]
again increasing from position 4 to last index => [1,2,3]
Example 2:
input [5, 5, 2, 1, 3, 4, 5]
valid output sequence with max selected items is [1, 3, 5, 4, 2, 5]
size of this output sequence is 6, so return the value 6
Explanation:
increasing from position 0 to 2 => [1,3,5]
decreasing from position 2 to 4 => [5,4,2]
again increasing from position 4 to last index => [2,5]
Example 3:
input [1, 3, 5, 4, 2, 6, 8, 7, 9]
Output: 9
Example 4:
input = [1,100]
for this input we can get the updated sequence as [100, 1]
a) increasing part = [100], here i = 0
b) decreasing part = [100, 1], here i=0, j=1
c) increasing part = [1], here j to end, j = 1
Observations: The last item in increasing part is same as first item of decreasing part in above discussion (i.e (a) and (b) groups), similarly the last item of decreasing part is same as first item of increasing part (i.e. (b) and (c) groups)
Constraints:
2 <= input size <= 105
1 <= input element <= 109
input contains at least 2 unique elements.
The program should return the size of the output sequence.
I tried to solve this using a TreeMap:
public static int solve(List<Integer> list) {
int n = list.size();
TreeMap<Integer, Integer> map = new TreeMap<>();
int min = Integer.MAX_VALUE;
for(int e : list) {
min = Math.min(min, e);
map.put(e, map.getOrDefault(e, 0)+1);
}
int result = 1;
map.put(min, map.getOrDefault(min,0)-1);
if(map.get(min) <=0) map.remove(min);
while(true) {
Integer key = map.higherKey(min);
if(key == null) break;
map.put(key, map.getOrDefault(key,0)-1);
if(map.get(key) <=0) map.remove(key);
min = key;
result++;
}
int max = min;
while(true) {
Integer key = map.lowerKey(max);
if(key == null) break;
map.put(key, map.getOrDefault(key,0)-1);
if(map.get(key) <=0) map.remove(key);
max = key;
result++;
}
min = max;
while(true) {
Integer key = map.higherKey(min);
if(key == null) break;
map.remove(key);
min = key;
result++;
}
return result;
}
public static void main(String[] args) {
System.out.println(solve(List.of(1, 3, 5, 4, 2, 6, 8, 7, 9))); // Expected output: 9
System.out.println(solve(List.of(5, 5, 2, 1, 3, 4, 5))); // Expected output: 6
System.out.println(solve(List.of(1, 100))); // Expected output: 2
System.out.println(solve(List.of(2, 1, 3, 3, 1, 2, 1, 2, 3))); // Expected output: 7
}
The code fails for input 5, 5, 2, 1, 3, 4, 5, it returns 5 as output instead of 6. This is due to my generated array becoming [1,2,3,4,5] with 5 items also not following increasing-decreasing-increasing pattern
So I am using wrong approach to solve this problem, what is the correct approach to solve this problem.
We need at least two distinct values to have a solution -- if this is not the case we cannot satisfy the constraints, namely that "Items from i to j should be in decreasing order strictly" and "i < j".
The maximum value is a good value to use at index 𝑖, and the minimum value at index 𝑗. All other distinct values can be used once between those two indices, forming the middle, descending section. If there are copies of these "other" values, they can be used once more in the first, ascending section, and again in the third, ascending section, meaning that we can use up to three occurrences of the same value. This is not so for the minimum and maximum value. The maximum (it index 𝑖) can only be used again as the ending value of the third section, while the minimum (at index 𝑗) can only be used again as the starting value of the first section, meaning those two values can be used up to twice only.
It is not needed to actually build the new list as we only need to return the size of that list.
With these observations we get to this algorithm:
public static int solve(List<Integer> list) {
Map.Entry<Integer, Integer> min, max;
// Get all frequencies
Map<Integer, Integer> counts = new HashMap<>();
list.forEach(s -> counts.merge(s, 1, Math::addExact));
if (counts.size() < 2) return 0; // No solution
// Get minimum and its frequency, and use at most 2 copies
min = Collections.min(counts.entrySet(), Map.Entry.comparingByKey());
counts.remove(min.getKey());
int result = Math.min(2, min.getValue());
// Similar approach for the maximum:
max = Collections.max(counts.entrySet(), Map.Entry.comparingByKey());
counts.remove(max.getKey());
result += Math.min(2, max.getValue());
// All other values can be used at most 3 times
for (int count : counts.values()) {
result += Math.min(3, count);
}
return result;
}
I've not used a (sorted) TreeMap here, as processing all input values into a TreeMap would lead to a O(𝑛log𝑛) complexity. Using a HashMap we can achieve a linear time complexity for this process.
Finding both minimum and maximum again represents O(𝑛) time complexity (in the worst case where all 𝑛 input values are distinct), and also the final loop to accumulate the result has a linear time complexity.
This brings the total time complexity to O(𝑛).
NB: in practice the overhead of the repeated iteration over the values may make the benefit over using a sorted container only apparent for very large inputs.