☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

Program for Least Recently Used (LRU) Page Replacement Algorithm

Medium TUF ID 2859 A2Z

Java source ↗ Edit this article ↗

Problem

Main memory has room for capacity pages (called frames). A program references pages in the order given by pages. When a referenced page is already in memory, it is a hit. Otherwise it is a page fault: the page must be loaded, and if memory is full, one resident page is evicted first. Under the Least Recently Used (LRU) policy the victim is the resident page whose most recent reference lies furthest in the past. Return the number of page faults.

Constraints (GfG version): 1 ≤ n ≤ 1000, 1 ≤ capacity ≤ 100, 1 ≤ pages[i] ≤ 1000. The hash-map approaches below handle n = 10^5 just as easily.

LRU is a greedy rule: the ideal policy (Belady’s optimal algorithm) evicts the page that will be used furthest in the future, which needs knowledge we do not have. LRU uses the past as a stand-in for the future and evicts the page that has gone unused the longest.

Example 1

pages = [5, 0, 1, 3, 2, 4, 1, 0, 5], capacity = 4
answer = 8

The first four references fill memory (4 faults). Then 2 evicts 5, 4 evicts 0, 1 is a hit, 0 evicts 3 and 5 evicts 2: four more faults, eight in total. The full trace is in the table under Approach 2.

Example 2

pages = [1, 2, 1, 3, 2], capacity = 10
answer = 3

Memory never fills, so only the first reference to each of the three distinct pages faults.

Approach 1: Brute force, a list in recency order

Intuition. Keep the resident pages in a list ordered from least recently used (front) to most recently used (back). On every reference, look the page up. On a hit, pull it out of the list. On a fault, count it and, if the list is full, drop the front element, which is by construction the least recently used. Either way, append the page at the back, because it is now the most recently used.

Algorithm.

  1. frames is an empty list, faults = 0.
  2. For each page: find its position with indexOf.
    • Found: remove it from that position.
    • Not found: faults++; if frames.size() == capacity, remove index 0.
  3. Append page. Return faults at the end.
static int bruteForce(int[] pages, int capacity) {
    List<Integer> frames = new ArrayList<>();                 // index 0 = least recently used
    int faults = 0;
    for (int page : pages) {
        int pos = frames.indexOf(page);
        if (pos >= 0) {
            frames.remove(pos);                               // hit: re-added at the most recent end below
        } else {
            faults++;
            if (frames.size() == capacity) frames.remove(0);  // memory full: evict the least recently used page
        }
        frames.add(page);
    }
    return faults;
}

Complexity. Time O(n · C) with C = capacity: indexOf and removal from an ArrayList both shift or scan up to C elements. Space O(C). For the GfG limits that is at most 10^5 steps, so this alone passes; the next approach is what you would use as a real cache.

A Java trap hides here: frames holds Integer, so frames.remove(pos) with an int removes by index, while frames.remove(Integer.valueOf(page)) would remove by value. The code deliberately uses the index it just found.

Approach 2: Optimal, hash map plus doubly linked list

Intuition. The list approach needs two things per reference: “is this page resident, and where?” and “move this entry to the most-recent end, or drop the least-recent one”. A HashMap from page to node answers the first in O(1). A doubly linked list makes the second O(1) too, because a node can unlink itself through its prev and next pointers without any scanning. Two sentinel nodes, head and tail, remove every null check: the most recent page always sits at head.next and the least recent at tail.prev.

Algorithm.

  1. Map where is empty; link head ⇄ tail.
  2. For each page:
    • If where has it, unlink its node.
    • Otherwise faults++; if the map already holds capacity pages, unlink tail.prev and remove its page from the map; create a new node and put it in the map.
    • Insert the node right after head.
  3. Return faults.
static class Node {
    int page;
    Node prev, next;

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

static int optimal(int[] pages, int capacity) {
    Map<Integer, Node> where = new HashMap<>();
    Node head = new Node(-1), tail = new Node(-1);            // sentinels: head.next is most recent, tail.prev least recent
    head.next = tail;
    tail.prev = head;
    int faults = 0;
    for (int page : pages) {
        Node node = where.get(page);
        if (node != null) {
            unlink(node);                                     // hit: re-inserted at the front below
        } else {
            faults++;
            if (where.size() == capacity) {                   // memory full: evict the node just before tail
                Node lru = tail.prev;
                unlink(lru);
                where.remove(lru.page);
            }
            node = new Node(page);
            where.put(page, node);
        }
        node.next = head.next;                                // insert right after head
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    return faults;
}

static void unlink(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

Dry run on example 1 (frames listed least recent to most recent):

page result evicted frames after
5 fault - 5
0 fault - 5 0
1 fault - 5 0 1
3 fault - 5 0 1 3
2 fault 5 0 1 3 2
4 fault 0 1 3 2 4
1 hit - 3 2 4 1
0 fault 3 2 4 1 0
5 fault 2 4 1 0 5

Eight faults. Notice the hit on page 1: it moves 1 to the most-recent end, which is why 3, not 1, is evicted when 0 comes back. A FIFO policy would ignore that hit and evict 1 instead.

Complexity. Time O(n): each reference does a constant number of map operations (average O(1)) and pointer updates. Space O(C): the map and list never hold more than capacity pages.

Approach 3: Optimal, LinkedHashMap in access order

Intuition. Java already ships the structure from Approach 2. LinkedHashMap is a hash map whose entries are also threaded on a doubly linked list. Passing true as the third constructor argument switches that list from insertion order to access order: every get or put of an existing key moves the entry to the end. Iteration then starts at the least recently used key, so the eviction victim is simply the first key of keySet().

One detail matters: containsKey does not count as an access. That is why the hit branch calls get explicitly; without it, hits would not refresh recency and the cache would behave like FIFO.

static int optimalLinkedHashMap(int[] pages, int capacity) {
    LinkedHashMap<Integer, Boolean> frames = new LinkedHashMap<>(16, 0.75f, true);   // true = iterate in access order
    int faults = 0;
    for (int page : pages) {
        if (frames.containsKey(page)) {
            frames.get(page);                                 // get() counts as an access and moves the page to the end
        } else {
            faults++;
            if (frames.size() == capacity) {
                int lru = frames.keySet().iterator().next();  // first key in access order = least recently used
                frames.remove(lru);
            }
            frames.put(page, Boolean.TRUE);
        }
    }
    return faults;
}

Complexity. Same as Approach 2: O(n) time and O(C) space. In production code people often subclass LinkedHashMap and override removeEldestEntry to evict automatically; the explicit version above keeps the fault counting visible.

Edge cases and pitfalls