Problem Description Amazon needs to distribute pri...

java
import java.util.*;

public static List<Integer> assignPrizes(List<Integer> points, List<Integer> values) {
    int n = points.size();
    // Count participants per distinct score (sorted ascending)
    TreeMap<Integer, Integer> scoreCount = new TreeMap<>();
    for (int p : points) scoreCount.merge(p, 1, Integer::sum);
    int m = scoreCount.size();

    // Available prize values with multiplicities (sorted)
    TreeMap<Integer, Integer> avail = new TreeMap<>();
    for (int v : values) avail.merge(v, 1, Integer::sum);

    // Quick impossibility checks
    int totalNeeded = n;
    int totalAvail = values.size();
    if (totalAvail < totalNeeded) return Collections.emptyList(); // not enough prizes at all
    if (m > avail.size()) {
        // need m strictly increasing prize values; if fewer distinct values exist than groups, impossible
        // (even if counts are large)
        // Still could be possible if some values have 0 after consumption? No—distinct strictly increasing values required.
        // So return empty.
        return Collections.emptyList();
    }

    // Map scores to their index and required counts
    int idx = 0;
    int[] sizes = new int[m];
    int[] scoresByIdx = new int[m];
    Map<Integer, Integer> scoreToIdx = new HashMap<>();
    for (Map.Entry<Integer, Integer> e : scoreCount.entrySet()) {
        scoresByIdx[idx] = e.getKey();
        sizes[idx] = e.getValue();
        scoreToIdx.put(e.getKey(), idx);
        idx++;
    }

    // Assigned prize value per score index (null if unassigned)
    Integer[] assigned = new Integer[m];

    // Helper to reduce count in a TreeMap (remove key if zero)
    final class Util {
        void dec(TreeMap<Integer,Integer> tm, int key, int by) {
            int left = tm.getOrDefault(key, 0) - by;
            if (left < 0) throw new IllegalStateException("negative stock");
            if (left == 0) tm.remove(key);
            else tm.put(key, left);
        }
        Integer nextKeyAtLeast(TreeMap<Integer,Integer> tm, int atLeast) {
            return tm.ceilingKey(atLeast);
        }
    }
    Util util = new Util();

    // Greedy feasibility check for remaining groups given current (and tentative) availability & assignments.
    // Tries to assign the smallest possible valid value to each remaining group in increasing score order.
    java.util.function.BiFunction<TreeMap<Integer,Integer>, Integer[], Boolean> feasible =
        (stock, assignedNow) -> {
            int prev = Integer.MIN_VALUE; // last assigned value
            // Iterate groups in ascending score order
            for (int i = 0; i < m; i++) {
                Integer fixed = assignedNow[i];
                // Determine upper bound from the next higher already-assigned group (if any)
                int ub = Integer.MAX_VALUE;
                for (int j = i + 1; j < m; j++) {
                    if (assignedNow[j] != null) { ub = assignedNow[j]; break; }
                }
                if (fixed != null) {
                    if (fixed <= prev || fixed >= ub) return false; // violates strictly increasing order
                    prev = fixed;
                    continue;
                }
                // Need to pick the smallest value >= prev+1 and < ub with enough copies
                Integer cand = stock.ceilingKey(prev == Integer.MIN_VALUE ? Integer.MIN_VALUE : prev + 1);
                while (cand != null && cand < ub) {
                    int have = stock.get(cand);
                    if (have >= sizes[i]) {
                        // consume for feasibility check
                        int left = have - sizes[i];
                        if (left == 0) stock.remove(cand);
                        else stock.put(cand, left);
                        prev = cand;
                        // move on to next group
                        break;
                    }
                    cand = stock.higherKey(cand);
                }
                if (cand == null || cand >= ub) return false; // none fits
            }
            return true;
        };

    // Iterate original indices to ensure lexicographically smallest output
    for (int pos = 0; pos < n; pos++) {
        int s = points.get(pos);
        int k = scoreToIdx.get(s);
        if (assigned[k] != null) continue; // already fixed for this score group

        // Bounds from neighbors already assigned
        int lb = Integer.MIN_VALUE; // strictly greater than lb
        for (int i2 = k - 1; i2 >= 0; i2--) {
            if (assigned[i2] != null) { lb = assigned[i2]; break; }
        }
        int ub = Integer.MAX_VALUE;  // strictly less than ub
        for (int i2 = k + 1; i2 < m; i2++) {
            if (assigned[i2] != null) { ub = assigned[i2]; break; }
        }

        // Try candidate prize values from smallest upward within (lb, ub)
        Integer cand = avail.ceilingKey(lb == Integer.MIN_VALUE ? Integer.MIN_VALUE : lb + 1);
        boolean placed = false;
        while (cand != null && cand < ub) {
            int have = avail.get(cand);
            if (have >= sizes[k]) {
                // Tentatively assign and check feasibility for all remaining groups
                TreeMap<Integer,Integer> stockCopy = new TreeMap<>(avail);
                // consume for current tentative
                int left = have - sizes[k];
                if (left == 0) stockCopy.remove(cand); else stockCopy.put(cand, left);

                Integer[] assignedTemp = assigned.clone();
                assignedTemp[k] = cand;

                if (feasible.apply(stockCopy, assignedTemp)) {
                    // Commit
                    assigned[k] = cand;
                    if (left == 0) avail.remove(cand); else avail.put(cand, left);
                    placed = true;
                    break;
                }
            }
            cand = avail.higherKey(cand == null ? Integer.MIN_VALUE : cand);
        }
        if (!placed) {
            // No valid assignment possible
            return Collections.emptyList();
        }
    }

    // Build output for each participant in original order
    Map<Integer,Integer> scoreToValue = new HashMap<>();
    for (int i2 = 0; i2 < m; i2++) scoreToValue.put(scoresByIdx[i2], assigned[i2]);

    List<Integer> out = new ArrayList<>(n);
    for (int p : points) out.add(scoreToValue.get(p));
    return out;
}

java
import java.util.*;

public static List<Integer> assignPrizes(List<Integer> points, List<Integer> values) {
    int n = points.size();
    if (n == 0) return Collections.emptyList();

    // Count participants per distinct score (ascending by score)
    TreeMap<Integer,Integer> scoreCnt = new TreeMap<>();
    for (int p : points) scoreCnt.merge(p, 1, Integer::sum);

    int m = scoreCnt.size();
    int[] scores = new int[m], sizes = new int[m];
    Map<Integer,Integer> scoreToIdx = new HashMap<>();
    int t = 0;
    for (Map.Entry<Integer,Integer> e : scoreCnt.entrySet()) {
        scores[t] = e.getKey(); sizes[t] = e.getValue(); scoreToIdx.put(e.getKey(), t++);
    }

    // Available prize values with multiplicity
    TreeMap<Integer,Integer> stock = new TreeMap<>();
    for (int v : values) stock.merge(v, 1, Integer::sum);

    // Quick impossibility checks
    if (values.size() < n) return Collections.emptyList();
    if (stock.size() < m) return Collections.emptyList(); // need m distinct prize values

    // Order groups by first appearance in the original points array (lexicographic requirement)
    int[] firstPos = new int[m];
    Arrays.fill(firstPos, Integer.MAX_VALUE);
    for (int i = 0; i < n; i++) {
        int gi = scoreToIdx.get(points.get(i));
        if (firstPos[gi] == Integer.MAX_VALUE) firstPos[gi] = i;
    }
    Integer[] groupOrder = new Integer[m];
    for (int i = 0; i < m; i++) groupOrder[i] = i;
    Arrays.sort(groupOrder, Comparator.comparingInt(i -> firstPos[i]));

    Integer[] assigned = new Integer[m]; // prize value per score group (by ascending score index)

    // Feasibility: given partial 'assigned' and a stock snapshot, can we fill the rest greedily?
    java.util.function.BiFunction<Integer[], TreeMap<Integer,Integer>, Boolean> canFinish = (fix, inv) -> {
        int prev = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            // upper bound is the next already-fixed group's value (must be strictly less than it)
            int ub = Integer.MAX_VALUE;
            for (int j = i + 1; j < m; j++) if (fix[j] != null) { ub = fix[j]; break; }

            if (fix[i] != null) {
                if (fix[i] <= prev || fix[i] >= ub) return false;
                prev = fix[i];
                continue;
            }
            Integer cand = inv.ceilingKey(prev == Integer.MIN_VALUE ? Integer.MIN_VALUE : prev + 1);
            while (cand != null && cand < ub) {
                int have = inv.get(cand);
                if (have >= sizes[i]) {
                    // consume and go on
                    if (have == sizes[i]) inv.remove(cand);
                    else inv.put(cand, have - sizes[i]);
                    prev = cand;
                    break;
                }
                cand = inv.higherKey(cand);
            }
            if (cand == null || cand >= ub) return false;
        }
        return true;
    };

    // Assign groups in lexicographic order (by first appearance), picking the smallest viable value each time
    for (int g : groupOrder) {
        // bounds from neighboring score groups already fixed
        int lb = Integer.MIN_VALUE, ub = Integer.MAX_VALUE;
        for (int i = g - 1; i >= 0; i--) if (assigned[i] != null) { lb = assigned[i]; break; }
        for (int i = g + 1; i < m;  i++) if (assigned[i] != null) { ub = assigned[i]; break; }

        boolean placed = false;
        for (Integer cand = stock.ceilingKey(lb == Integer.MIN_VALUE ? Integer.MIN_VALUE : lb + 1);
             cand != null && cand < ub;
             cand = stock.higherKey(cand)) {

            int have = stock.get(cand);
            if (have < sizes[g]) continue;

            // try commit
            TreeMap<Integer,Integer> snap = new TreeMap<>(stock);
            if (have == sizes[g]) snap.remove(cand); else snap.put(cand, have - sizes[g]);

            Integer[] trial = assigned.clone();
            trial[g] = cand;
            if (canFinish.apply(trial, snap)) {
                assigned[g] = cand;
                if (have == sizes[g]) stock.remove(cand); else stock.put(cand, have - sizes[g]);
                placed = true;
                break;
            }
        }
        if (!placed) return Collections.emptyList(); // impossible
    }

    // Build output in participant order
    Map<Integer,Integer> scoreToPrize = new HashMap<>();
    for (int i = 0; i < m; i++) scoreToPrize.put(scores[i], assigned[i]);

    List<Integer> res = new ArrayList<>(n);
    for (int p : points) res.add(scoreToPrize.get(p));
    return res;
}