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.
Loading...
  1. Practice
  2. Algorithms
  3. Greedy
  4. Luck Balance
  5. Discussions

Luck Balance

  • RodneyShag + 1 comment

    Java O(n) solution

    Using QuickSelect, you can get an O(n) average-case solution.

    The full solution is in my HackerRank solutions. Here is a snippet of the code.

    public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int N = scan.nextInt();
    int K = scan.nextInt();
    ArrayList<Integer> contest = new ArrayList<>(N);
    int savedLuck = 0;
    for (int i = 0; i < N; i++) {
        int luck = scan.nextInt();
        int importance = scan.nextInt();
        if (importance == 0) {
            savedLuck += luck; // lose every non-important contest
        } else {
            contest.add(luck);
        }
    }
    scan.close();
        
    /* Compete in "important" contests */
    quickselect(contest, 0, contest.size() - 1, contest.size() - K);
    for (int i = 0; i < contest.size(); i++) {
        if (i < contest.size() - K) {
            savedLuck -= contest.get(i); // win contest
        } else {
            savedLuck += contest.get(i); // lose contest
        }
    }
    System.out.println(savedLuck);
}

    Let me know if you have any questions.

    • tat_lim + 2 comments

      Agreed! The average-case solution for QuickSelect is indeed O(n). Unfortunately, when the list is sorted (or "nearly" sorted), your algorithm will degenerate to the worst-case of O(n*n)... :(

      • RodneyShag + 1 comment

        Hi. I agree, O(n^2) can happen, but this worst-case O(n^2) happens extremely rarely. It's O(n) 99.99%+ of the time for randomly generated data. To get the degenerate case, the user would have to provide data in a specific way to break quickselect based on how the pivot is selected. Such cases are mostly a concern if a hacker is intentionally trying to break quickselect.

        Quickselect doesn't become O(n^2) just because the data is sorted. 3 things have to align for the runtime to reach O(n^2), for sorted data, here are the 3 things (from Wikipedia)
        1) Data is sorted
        2) User is searching for the maximum element in a set (which is usually not the case, since a sorting algorithm is not a good way to find the max element)
        3) The first element is used as a pivot

        If you look into how I implemented QuickSelect you will see that I do not choose the starting element as a pivot, so my code will still run in O(n) on a sorted list.

        As a personal preference, I'm happy getting O(n) 99% of the time with the rare case of O(n^2).

        Cheers!

        • tat_lim + 0 comments

          Agreed! For a high-volume website, however, we cannot bet on the worst-case of O(n*n) even if it has a mere chance of 0.01%, especially when millions of searches are conducted per day. FYI, 1 million multiplied by 0.01% = 100.

      • rhinodavid + 1 comment

        A good implementation of the algorithm will have randomization built in, such that the order of the list does not matter.

        • tat_lim + 0 comments

          Agreed! On the other hand, even with randomization builtin, QuickSelect still has the worst-case of O(n*n), however improbable it may be.