Marks from Ranks

Problem Overview

The intervals are sorted and disjoint, so the valid marks form one increasing sequence without listing them.

Intuition

The intervals are sorted and disjoint, so the valid marks form one increasing sequence without listing them. Interval i contributes r[i] - l[i] + 1 consecutive ranks. A prefix of those sizes tells you, for any rank, which interval it lands in. Once you have that interval, the mark is just an offset from the right (or left) endpoint.

Algorithm

1Build prefix[i] = total number of marks in intervals 0..i.
2For each query rank q, binary search the first i with prefix[i] >= q.
3The mark is r[i] - (prefix[i] - q), which is the q-th mark counted from the left of the merged sequence.
4Collect those marks in query order and return the list.

Example Walkthrough

Input: l = [1, 8], r = [3, 10], rank = [1, 5, 4]

1. Intervals [1,3] and [8,10] give 3 + 3 = 6 marks. prefix = [3, 6].
2. Rank 1 sits in interval 0: mark = 3 - (3-1) = 1.
3. Rank 5 sits in interval 1: mark = 10 - (6-5) = 9. Rank 4: mark = 10 - (6-4) = 8.

Output: [1, 9, 8]

Common Pitfalls

• Do not expand every integer in each interval. Wide ranges make that time and memory blow up.
• Ranks are 1-based. Compare prefix against q, not q-1, when locating the interval.
• Use a long prefix if interval lengths can overflow int when summed.
• The leftover-list merge in the naive code is wrong when l and r are parallel interval endpoints, not two sorted streams.

Marks from Ranks.java

Java

// Approach: Each interval [l[i], r[i]] contributes (r[i]-l[i]+1) ranks. Prefix-
// sum those counts, then for each query rank use binary search to find the
// interval and compute mark as r[idx] - (prefix[idx] - rank).
// Complexity: O(n + q log n) time and O(n) extra space (q = rank.length).

import java.util.*;

class Solution {

    public ArrayList<Integer> getMarks(int[] l, int[] r, int[] rank) {
        int n = l.length;
        long[] prefix = new long[n];

        for (int i = 0; i < n; i++) {
            prefix[i] = (r[i] - l[i] + 1L) + (i > 0 ? prefix[i - 1] : 0);
        }

        ArrayList<Integer> ans = new ArrayList<>();

        for (int q : rank) {
            int lo = 0;
            int hi = n - 1;

            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (prefix[mid] >= q) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }

            ans.add((int) (r[lo] - (prefix[lo] - q)));
        }

        return ans;
    }
}

Was this solution helpful?