146. LRU Page Replacement - Count Page Faults

Given a cache of capacity n and a sequence of m page requests, simulate the Least Recently Used (LRU) page replacement policy: on a page already in the cache, mark it as most recently used; on a page not in the cache, it's a page fault - insert it (evicting the least recently used page first if the cache is full). Print the total number of page faults.

Input: The first line contains an integer n, the cache capacity. The second line contains an integer m, the number of page requests. The third line contains m space-separated integers, the sequence of requested pages. Output: Print a single integer - the total number of page faults.

1 <= n <= 1000, 1 <= m <= 10^5

Every cache HIT still requires updating recency (moving that page to the front) - forgetting this update is a common bug, since only cache MISSES count as faults, but hits still change future eviction order.

Simulate the Least Recently Used cache eviction policy and count how many page faults (cache misses) occur. Brute force: Use a plain array or list to track cache contents and recency, scanning linearly to find the least-recently-used item to evict - this costs O(cache size) per operation, potentially slow for large caches with many requests. Optimised: A hash map (for O(1) lookup of whether a page is cached) combined with a doubly linked list (for O(1) 'move to front' and O(1) eviction from the back) together give every single operation - hit, fault, and eviction - O(1) time, rather than needing to scan the whole cache each time.

Combine a hash map from page to node with a doubly linked list that keeps cache entries ordered by recency. A hit looks up the node in O(1) via the map and unlinks/relinks it to the most-recently-used end in O(1); a fault inserts a new node in O(1) and, if over capacity, removes the least-recently-used end, also in O(1) since it's a direct pointer. Every single operation is constant time, so the whole simulation costs time proportional only to the number of requests. Time: O(m) Space: O(n)

Represent the cache as a plain list. For every page request, scan the entire list linearly to check whether the page is already present; if present, remove it from its current position and re-insert it at the most-recently-used end, and if absent, count a fault, evicting the least-recently-used end first if the cache is already full. Both the membership check and the reordering cost time proportional to the cache size on every single request. Time: O(n * m) Space: O(n)

Keep a hash set for instant membership testing ("is this page currently cached") alongside a list that records usage order. A miss is now detected in O(1) instead of scanning the whole list, so pages that clearly aren't cached resolve instantly; only a hit still requires locating and moving that entry within the order-tracking list, which remains a linear operation in the worst case. Time: O(n * m) worst case, much smaller constant on misses Space: O(n)

1. Use a hash map plus a doubly linked list (or an equivalent ordered structure supporting 'move to front') for O(1) lookup and eviction. 2. On a page already in the cache: it's a HIT, not a fault - just mark it as most recently used (move it to the front). 3. On a page NOT in the cache: it's a FAULT - insert it (evicting the least recently used page first if the cache is already full).

Time: O(m), where m is the number of page requests - each request is handled in O(1) with the hash-map-plus-linked-list structure. Space: O(n), for the cache holding at most n pages plus its recency-ordering structure.

n = 1 (the cache holds only one page), a request sequence that repeatedly reuses the same small set of pages, and m at its maximum of 10^5 to confirm the LRU simulation runs efficiently.

Be ready to explain WHY a plain array-based recency tracker is insufficient for true O(1) performance - moving an item to the 'front' of a plain array requires shifting other elements, which a doubly linked list avoids entirely via pointer relinking.