leetcode-program

Question 632: Smallest Range

Link

Solution

This is a two pointers problem.

First, we can easily prove the following facts:

• The boundaries of the range should be in the given numbers.

If we were maintaining a set, which contains k numbers, each belongs to an independent row. Then selecting the smallest and biggest number in the set as the boundaries and this would be a valid range obviously. So now we just need to search all the sets and find the smallest range. This set can be maintained with two pointers.

Initially, creates

• a heap which contains the pointer to first element (also means smallest number) of each row.
• a max variable, indicates the max value of the heap
• a range variable, indicates the current optimal answer’s range size, INF initially

In a loop,

• takes and removes the top of the heap, records as top, and calculates the max minus top
• if the result is smaller than the current answer’s, then update range
• add the next element of top if it has a next, otherwise break the loop

Then we would get the optimal answer.

Code

Java

public class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        List<Node> rows = nums.stream().map(row -> {
            Iterator<Integer> it = row.iterator();
            Node start = new Node(it.next());
            Node node = start;
            while (it.hasNext()) {
                Node next = new Node(it.next());
                node.next = next;
                node = next;
            }
            return start;
        }).collect(Collectors.toList());
        PriorityQueue<Node> heap = new PriorityQueue<>(rows);
        int[] ret = null;
        int range = Integer.MAX_VALUE;
        int max = rows.stream().mapToInt(raw -> raw.v).max().getAsInt();
        while (true) {
            Node top = heap.poll();
            if (max - top.v < range) {
                range = max - top.v;
                ret = new int[]{top.v, max};
            }
            if (top.next != null) {
                max = Math.max(max, top.next.v);
                heap.add(top.next);
            } else {
                break;
            }
        }

        return ret;
    }

    private static class Node implements Comparable<Node> {
        int v;

        Node next;

        Node(int v) {
            this.v = v;
        }

        @Override
        public int compareTo(Node o) {
            return v - o.v;
        }
    }
}

This site is open source. Improve this page.