HackerRank-Solutions/General Programming/Basic Programming/Electronics Shop/Solution.java

//     Author: Rodney Shaghoulian
//     Github: github.com/RodneyShag
// HackerRank: hackerrank.com/RodneyShag

import java.util.Scanner;
import java.util.Arrays;

// Algorithm: 
//     1. Sort both arrays.
//     2. Linearly walk through both arrays (at the same time).
//        If the combined price is unaffordable, find a cheaper harddrive (j--).
//        If the combined price is too low, update "max", and find a more expensive keyboard (i++)

// Time complexity: O(n log n + m log m)
public class Solution {
    static int getMoneySpent(int[] keyboards, int[] drives, int s) {
        Arrays.sort(keyboards); // O(n log n) time complexity
        Arrays.sort(drives);    // O(m log m) time complexity
        int max = -1;
        int i = 0;
        int j = drives.length - 1;
        while (i < keyboards.length && j >= 0) { // O(n + m) time complexity
            int cost = keyboards[i] + drives[j];
            if (cost > s) {
                j--; // look for a cheaper hard drive
            } else {
                if (cost > max) {
                    max = cost;
                }
                i++; // look for a more expensive keyboard
            }
        }
        return max;
    }

    public static void main(String[] args) {
        /* Save input */
        Scanner scan = new Scanner(System.in);
        int s = scan.nextInt();
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[] keyboards = new int[n];
        for (int i = 0; i < n; i++) {
            keyboards[i] = scan.nextInt();
        }
        int[] drives = new int[m];
        for (int i = 0; i < m; i++) {
            drives[i] = scan.nextInt();
        }
        scan.close();
        
        /* Calculate result */
        int moneySpent = getMoneySpent(keyboards, drives, s);
        System.out.println(moneySpent);
    }
}