We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Permuting Two Arrays
  5. Discussions

Permuting Two Arrays

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

    You are viewing a single comment's thread. Return to all comments →

  • ryanfehr18
    5 years ago+ 2 comments

    Here is a detailed explanation of why sorting solves this problem:

    We can sort array A ascending and sort array B descending, and then because they are sorted we know that we are matching the highest possible from B with the lowest possible from A each time and if 1 of those fails then we know it is not possible. The reason we know this is true is because they are inversely sorted, so we have already made the optimal decision at each stage in terms of the amount of absolute difference we have 'wasted/extra' thus leaving us with the tightest bounding number to k for each index. Because it is the tightest bound number, there is no other permutation that will pass if 1 comparison fails.

    Optimizations to think about:

    • If you use a StringBuilder to build your answers to queries and then only make a single System.out call it will be much faster because I/O is slow
    • If we want to sort a int array in descending order using the built in libraries, we have to change it to an Integer[] which takes up 16 bytes per element compared to 4. So instead what we can do is sort the int[] ascending and just traverse it in reverse when comparing to view the elements in descending order

    Java Solution Here is my solution in Java that passes all cases in O(n log(n)) time with O(n) space.

    For more solutions like this check out the HackerRank Github repo here

    56|
    Permalink
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature