Skip to content

Instantly share code, notes, and snippets.

@shiny-eel

shiny-eel/Solution.java

Last active May 10, 2019 16:50
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save shiny-eel/ba3c0b40bb6515884db67306e6a01b96 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save shiny-eel/ba3c0b40bb6515884db67306e6a01b96 to your computer and use it in GitHub Desktop.
Download ZIP
[Minimum absolute sum of any pair] Minimum absolute sum of any pair of integers in an array. #codility #queues #sorting #java
Raw
readme.md

https://app.codility.com/programmers/lessons/15-caterpillar_method/min_abs_sum_of_two/

What I learned

  • Usage of ArrayDeque
  • Try to use addFirst(), addLast(), peekFirst(), peekLast(), pollFirst() as they have clear behaviour
  • Construction of the while loop
  • Use peek and poll/pop in different places
  • Run through an example in your head about what happens when a becomes empty
  • Where in the loop will it happen
  • How will the loop continue after
  • Here, the stop condition was either queue becoming empty.
  • Accounting for extra edge cases before starting the loop
  • i.e. lowest +ve * 2 or lowest -ve * 2
Raw
Solution.java
class Solution {
public int solution(int[] A) {
Arrays.sort(A);
// Split into -ve queue and +ve queue
ArrayDeque<Integer> negs = new ArrayDeque<>();
ArrayDeque<Integer> pos = new ArrayDeque<>();
for (int i = 0; i<A.length; i++) {
int el = A[i];
if (el >= 0) {
if (el == 0) return 0;
pos.addLast(el);
} else {
negs.addFirst(-el);
}
}
int min = Integer.MAX_VALUE;
if (!pos.isEmpty()) min = pos.peekFirst() * 2;
if (!negs.isEmpty()) min = Math.min(negs.peekFirst() * 2, min);
while(!pos.isEmpty() && !negs.isEmpty()) {
int posInt = pos.peekFirst();
int negInt = negs.peekFirst();
int diff = posInt - negInt;
min = Math.min(Math.abs(diff), min);
if (diff > 0) { // +ve is bigger
negs.pollFirst();
} else if (diff < 0) { // -ve bigger
pos.pollFirst();
} else { return 0; }
}
return min;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment