andreytim
BAN USERHere's the short code for the heap-reverse-filling approach in Java.
public int maxQaz(int[] arr) {
int max = 0;
TreeSet<Integer> heap = new TreeSet<>();
for (int i = arr.length-1; i >= 0; i--) {
heap.add(arr[i]);
max = Math.max(max, heap.tailSet(arr[i], false).size());
}
return max;
}
First, it seems like minimizing sum(|A[i]-B[i]|) is just the same as minimizing adjustment cost. It's, basically, just rephrasing the condition.
Second, I think it could be solved by BFS. Here's the working Java code:
public int adjust(int[] arr, int target) {
Set<String> visited = new HashSet<>();
visited.add(Arrays.toString(arr));
Map<String, int[]> parents = new HashMap<>();
parents.put(Arrays.toString(arr), null);
Queue<int[]> queue = new LinkedList<>();
queue.offer(arr);
int cost = 0;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
boolean adjusted = false;
for (int i = 0; i < curr.length-1; i++) {
if (Math.abs(curr[i] - curr[i+1]) > target) {
int[] A = Arrays.copyOf(curr, curr.length);
A[i] += (curr[i] - curr[i+1] > 0) ? -1 : 1;
if (visited.add(Arrays.toString(A))) {
parents.put(Arrays.toString(A), curr);
queue.offer(A);
}
A = Arrays.copyOf(curr, curr.length);
A[i+1] += (curr[i] - curr[i+1] > 0) ? 1 : -1;
if (visited.add(Arrays.toString(A))) {
parents.put(Arrays.toString(A), curr);
queue.offer(A);
}
adjusted = true;
}
}
if (!adjusted) {
System.out.println(Arrays.toString(curr));
while (parents.get(Arrays.toString(curr)) != null) {
cost++;
curr = parents.get(Arrays.toString(curr));
}
break;
}
}
return cost;
}
In terms of complexity, in a worst case at the each iteration we will put into our queue all increments and decrements (element-wise incremented and decremented arrays) for the each pair of consecutive elements in current array (O(n)) and we will do it "cost" number of times. As serialization of an Array is also linear we'll get O(n*n*cost). Maybe it's not the fastest but what I like here is that it's comparably easy to code, especially during the interview.
- andreytim December 10, 2014
Hey guys!
I've tried to make the compact OOP code for this problem using an InOrderIterator. Check it out:
- andreytim April 29, 2015