Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

LRU Page Replacement

Try it yourself
MediumProblemExternal link

Description

A computer's memory can hold only capacity pages at a time. A program requests pages one after another; the array pages lists the requests in order.

  • If the requested page is already in memory, it is a hit, and nothing needs to be loaded.
  • If it is not, it is a page fault: the page has to be loaded. If memory is already full, one page is removed first to make room.

With LRU (Least Recently Used) replacement, the page removed is the one whose most recent request is the oldest.

Memory starts empty. Return the number of page faults.

Examples

Example 1

Input: pages = [7, 0, 1, 2, 0, 3, 0, 4], capacity = 3

Output: 6

Explanation: Memory is listed from the least to the most recently used page.

  • 7, 0, 1: faults, memory [7, 0, 1]
  • 2: fault. Memory is full and 7 is the least recently used, so 2 replaces it: [0, 1, 2]
  • 0: hit, and 0 becomes the most recently used: [1, 2, 0]
  • 3: fault, replacing 1: [2, 0, 3]
  • 0: hit: [2, 3, 0]
  • 4: fault, replacing 2: [3, 0, 4]

That is 6 faults and 2 hits.

Example 2

Input: pages = [5, 0, 1, 3, 2, 4, 1, 0, 5], capacity = 4

Output: 8

Explanation: The first four requests fill memory. 2 replaces 5 and 4 replaces 0. The second 1 is the only hit. Then 0 replaces 3 and 5 replaces 2.

Example 3

Input: pages = [1, 1, 1, 1], capacity = 4

Output: 1

Explanation: Only the first request has to load page 1. The other three find it in memory.

Constraints

  • 1 ≤ pages.length ≤ 10^5
  • 1 ≤ capacity ≤ 10^4
  • 0 ≤ pages[i] ≤ 10^5

Editorial

Brute Force - Walking Back Through the Requests

Intuition

LRU's rule is about the past: remove the page whose last request is the oldest. The request list itself is a full record of the past, so it can answer that question directly.

Keep the pages in memory in a set. On a hit there is nothing to do, since the request list already records the use. On a fault with memory full, walk backwards from the current request. The pages in memory turn up in order of most recent use, so after capacity - 1 different memory pages have turned up, the one that has not turned up is the least recently used. Remove it and load the new page.

Step-by-Step Explanation

Example 1: pages = [7, 0, 1, 2, 0, 3, 0, 4], capacity = 3.

Step 1: 7, 0 and 1 are faults that fill memory: {7, 0, 1}.

Step 2: 2 is a fault with memory full. Walking back, 1 turns up, then 0. Two memory pages have turned up, and 7 has not, so 7 is the least recently used. 2 replaces it: {2, 0, 1}.

Step 3: 0 is a hit.

Step 4: 3 is a fault. Walking back, 0 turns up, then 2, so 1 is the least recently used. 3 replaces it: {2, 0, 3}.

Step 5: 0 is a hit.

Step 6: 4 is a fault. Walking back, 0 turns up, then 3, so 2 is replaced: {4, 0, 3}.

Step 7: The answer is 6 faults.

Brute Force: Walking Back Through the Requests — Top row: the requests; the pointer is the current one. Bottom row: memory. Orange requests were faults, green ones hits, and teal ones are being walked back over.

Algorithm

  1. Start with an empty set memory and faults = 0.
  2. For each request i with page p:
    • If p is in memory, continue.
    • Otherwise add 1 to faults. If memory is full, walk j backwards from i - 1, collecting the memory pages that turn up, until capacity - 1 different ones have. Remove the memory page that did not turn up.
    • Add p to memory.
  3. Return faults.

Code

class Solution {
public:
    int pageFaults(vector<int>& pages, int capacity) {
        unordered_set<int> memory;
        int faults = 0;
        for (int i = 0; i < (int)pages.size(); i++) {
            int page = pages[i];
            if (memory.count(page)) continue;  // a hit: the request history already records this use
            faults++;
            if ((int)memory.size() == capacity) {
                // Walk back through earlier requests. Pages in memory turn up in order of
                // most recent use, so the one never reached is the least recently used.
                unordered_set<int> seen;
                for (int j = i - 1; (int)seen.size() < capacity - 1; j--) {
                    if (memory.count(pages[j])) seen.insert(pages[j]);
                }
                for (int p : memory) {
                    if (!seen.count(p)) {
                        memory.erase(p);
                        break;
                    }
                }
            }
            memory.insert(page);
        }
        return faults;
    }
};
from typing import List

class Solution:
    def pageFaults(self, pages: List[int], capacity: int) -> int:
        memory = set()
        faults = 0
        for i, page in enumerate(pages):
            if page in memory:
                continue  # a hit: the request history already records this use
            faults += 1
            if len(memory) == capacity:
                # Walk back through earlier requests. Pages in memory turn up in order of
                # most recent use, so the one never reached is the least recently used.
                seen = set()
                j = i - 1
                while len(seen) < capacity - 1:
                    if pages[j] in memory:
                        seen.add(pages[j])
                    j -= 1
                lru = next(p for p in memory if p not in seen)
                memory.remove(lru)
            memory.add(page)
        return faults
class Solution {
    public int pageFaults(int[] pages, int capacity) {
        Set<Integer> memory = new HashSet<>();
        int faults = 0;
        for (int i = 0; i < pages.length; i++) {
            int page = pages[i];
            if (memory.contains(page)) continue;  // a hit: the request history already records this use
            faults++;
            if (memory.size() == capacity) {
                // Walk back through earlier requests. Pages in memory turn up in order of
                // most recent use, so the one never reached is the least recently used.
                Set<Integer> seen = new HashSet<>();
                for (int j = i - 1; seen.size() < capacity - 1; j--) {
                    if (memory.contains(pages[j])) seen.add(pages[j]);
                }
                for (int p : memory) {
                    if (!seen.contains(p)) {
                        memory.remove(p);
                        break;
                    }
                }
            }
            memory.add(page);
        }
        return faults;
    }
}

Complexity Analysis

Time Complexity: O(n²)

A walk back can pass many old requests. If one page is requested again and again, the other pages in memory drift far into the past, and each fault may walk back over most of the history.

Space Complexity: O(capacity)

The memory set and the set of pages seen during a walk each hold at most capacity pages.

Why This Approach Is Not Efficient

Every fault re-reads the history to answer the same question: when was each page in memory last used? With 10^5 requests, that can add up to billions of steps.

The answer changes in only one place per request, though: the page just requested becomes the most recent. So instead of re-reading the past, remember for each page in memory the moment it was last used, and update it on every request.

Better Approach - Remembering When Each Page Was Last Used

Intuition

Keep a map last_used from each page in memory to the index of its most recent request. On every request, set last_used[page] = i. On a fault with memory full, the least recently used page is the one with the smallest last_used value: find it, remove it, and load the new page.

Step-by-Step Explanation

Example 1 again.

Step 1: 7, 0 and 1 load at times 0, 1 and 2.

Step 2: 2 arrives at time 3. The smallest last use is 7's (time 0), so 2 replaces 7.

Step 3: 0 arrives at time 4: a hit, and its last use becomes 4.

Step 4: 3 arrives at time 5. The smallest last use is now 1's (time 2), so 3 replaces 1.

Step 5: 0 arrives at time 6: a hit, last use 6.

Step 6: 4 arrives at time 7. The smallest last use is 2's (time 3), so 4 replaces 2.

Step 7: The answer is 6 faults.

Better Approach: Remembering When Each Page Was Last Used — Each cell is a page in memory, with the time of its last request underneath. Orange is the page with the oldest last use, about to be replaced; indigo was just loaded; green was just hit.

Algorithm

  1. Start with an empty map last_used and faults = 0.
  2. For each request i with page p:
    • If p is not in last_used: add 1 to faults, and if the map already holds capacity pages, remove the page with the smallest last_used value.
    • Set last_used[p] = i.
  3. Return faults.

Code

class Solution {
public:
    int pageFaults(vector<int>& pages, int capacity) {
        unordered_map<int, int> lastUsed;  // page in memory -> index of its most recent request
        int faults = 0;
        for (int i = 0; i < (int)pages.size(); i++) {
            int page = pages[i];
            if (!lastUsed.count(page)) {
                faults++;
                if ((int)lastUsed.size() == capacity) {
                    int lru = -1, oldest = INT_MAX;
                    for (auto& [p, t] : lastUsed) {
                        if (t < oldest) {
                            oldest = t;
                            lru = p;
                        }
                    }
                    lastUsed.erase(lru);
                }
            }
            lastUsed[page] = i;
        }
        return faults;
    }
};
from typing import List

class Solution:
    def pageFaults(self, pages: List[int], capacity: int) -> int:
        last_used = {}  # page in memory -> index of its most recent request
        faults = 0
        for i, page in enumerate(pages):
            if page not in last_used:
                faults += 1
                if len(last_used) == capacity:
                    lru = min(last_used, key=last_used.get)  # the oldest last use
                    del last_used[lru]
            last_used[page] = i
        return faults
class Solution {
    public int pageFaults(int[] pages, int capacity) {
        Map<Integer, Integer> lastUsed = new HashMap<>();  // page in memory -> index of its most recent request
        int faults = 0;
        for (int i = 0; i < pages.length; i++) {
            int page = pages[i];
            if (!lastUsed.containsKey(page)) {
                faults++;
                if (lastUsed.size() == capacity) {
                    int lru = -1, oldest = Integer.MAX_VALUE;
                    for (Map.Entry<Integer, Integer> e : lastUsed.entrySet()) {
                        if (e.getValue() < oldest) {
                            oldest = e.getValue();
                            lru = e.getKey();
                        }
                    }
                    lastUsed.remove(lru);
                }
            }
            lastUsed.put(page, i);
        }
        return faults;
    }
}

Complexity Analysis

Time Complexity: O(n × capacity)

A hit is O(1), but each fault scans every page in memory for the smallest time.

Space Complexity: O(capacity)

The map holds at most capacity pages.

Why This Approach Is Not Efficient

Finding the smallest time means scanning all of memory on every fault. With 10^5 requests and room for 10^4 pages, that can reach 10^9 steps.

What the scan looks for, the least recently used page, is always the same end of one ordering: pages sorted by last use. If memory is kept in that order as requests arrive, the page to remove is always at the front, and no scan is needed.

Optimal Approach - Keeping Memory in Order of Use

Intuition

Keep the pages in memory in order of their last use, from the least recently used at the front to the most recently used at the back:

  • Hit: move the page to the back.
  • Fault: if memory is full, remove the page at the front. Then add the new page at the back.

Every step touches only the front, the back, or one known page, so each request is O(1) with the right structure: a doubly linked list holding the order, plus a hash map from each page to its node, so a hit can find and unlink its page without searching. This is exactly the structure behind the LRU Cache problem, which builds it by hand.

Most languages already provide it: Python's OrderedDict (move_to_end, popitem(last=False)), Java's LinkedHashSet, JavaScript's Map (which keeps keys in insertion order), and in C++ a std::list together with an unordered_map from page to list position.

Why LRU never gets worse with more memory. For the simpler first-in, first-out rule (remove the page loaded longest ago, even if it was just used), more memory can mean more faults. On the requests 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, first-in, first-out makes 9 faults with room for 3 pages but 10 with room for 4. This is Bélády's anomaly. LRU makes 10 and then 8, and it can never get worse: memory under LRU always holds the capacity most recently used different pages, so a bigger memory holds everything a smaller one does and more. Every hit with less memory is still a hit with more.

Step-by-Step Explanation

Example 1. Memory is written from least to most recently used.

Step 1: 7, 0 and 1 are faults: [7, 0, 1].

Step 2: 2 is a fault with memory full. Remove the front, 7, and add 2 at the back: [0, 1, 2].

Step 3: 0 is a hit. The map finds its node at once; move it to the back: [1, 2, 0].

Step 4: 3 is a fault. Remove the front, 1: [2, 0, 3].

Step 5: 0 is a hit. Move it to the back: [2, 3, 0].

Step 6: 4 is a fault. Remove the front, 2: [3, 0, 4].

Step 7: The answer is 6 faults, and no request needed a search.

Optimal Approach: Keeping Memory in Order of Use — Memory as a doubly linked list, least recently used (LRU) at the front and most recently used (MRU) at the back. Orange is the page about to be removed, indigo was just loaded, green was just hit.

Algorithm

  1. Keep memory as an ordered structure from least to most recently used (a doubly linked list plus a hash map from page to node), and faults = 0.
  2. For each page p in pages:
    • If p is in memory, move it to the most recent end.
    • Otherwise add 1 to faults. If memory holds capacity pages, remove the least recently used one from the front. Add p at the most recent end.
  3. Return faults.

Code

class Solution {
public:
    int pageFaults(vector<int>& pages, int capacity) {
        list<int> order;                                // least to most recently used
        unordered_map<int, list<int>::iterator> where;  // page -> its place in order
        int faults = 0;
        for (int page : pages) {
            auto it = where.find(page);
            if (it != where.end()) {
                order.erase(it->second);  // a hit: moved to the most recent end below
            } else {
                faults++;
                if ((int)order.size() == capacity) {
                    where.erase(order.front());  // evict the least recently used
                    order.pop_front();
                }
            }
            order.push_back(page);
            where[page] = prev(order.end());
        }
        return faults;
    }
};
from collections import OrderedDict
from typing import List

class Solution:
    def pageFaults(self, pages: List[int], capacity: int) -> int:
        memory = OrderedDict()  # pages from least to most recently used
        faults = 0
        for page in pages:
            if page in memory:
                memory.move_to_end(page)  # a hit: now the most recently used
            else:
                faults += 1
                if len(memory) == capacity:
                    memory.popitem(last=False)  # evict the least recently used
                memory[page] = True
        return faults
class Solution {
    public int pageFaults(int[] pages, int capacity) {
        LinkedHashSet<Integer> memory = new LinkedHashSet<>();  // least to most recently used
        int faults = 0;
        for (int page : pages) {
            if (memory.remove(page)) {
                memory.add(page);  // a hit: re-added as the most recently used
            } else {
                faults++;
                if (memory.size() == capacity) {
                    memory.remove(memory.iterator().next());  // evict the least recently used
                }
                memory.add(page);
            }
        }
        return faults;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each request is one hash map lookup plus a constant number of list changes, O(1) on average.

Space Complexity: O(capacity)

The list and the map each hold at most capacity pages.

Comparison:

ApproachTimeExtra space
Walk back through the historyO(n²)O(capacity)
Remember last-use timesO(n × capacity)O(capacity)
Keep memory in order of useO(n)O(capacity)