Copy List with Random Pointer

📋

Copy List with Random Pointer

Edge cases:

</>

IDE

def copyRandomList(head: 'Node') -> 'Node':public Node copyRandomList(Node head)Node* copyRandomList(Node* head)function copyRandomList(head)

def copyRandomList(head):
    # Write your solution here
    pass

class Solution {
    public Node copyRandomList(Node head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

Node* copyRandomList(Node* head) {
    // Write your solution here
    return nullptr;
}

function copyRandomList(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Random pointers in copied list point to original nodes instead of copied nodes.Forgot to use a mapping from original to copied nodes when assigning random pointers.✅ Use a dictionary/map to store original->copy node mapping and assign random pointers using this map.

Wrong: Function crashes or returns non-null for empty input.No base case handling for empty input (null head).✅ Add a check at the start: if head is null, return null immediately.

Wrong: Infinite recursion or timeout on inputs with cycles in random pointers.No visited map or memoization to handle cycles in random pointers.✅ Use a map to track visited nodes and avoid revisiting during recursion or iteration.

Wrong: Random pointers in copied list do not preserve shared references, creating multiple copies of the same node.Assigning random pointers without reusing copied nodes from the map.✅ Always assign random pointers using the map to ensure shared references point to the same copied node.

Wrong: Solution times out on large inputs.Using exponential or quadratic time approach instead of O(n).✅ Implement O(n) time solution using hash map or node weaving technique.

✓

Test Cases

Handle base cases like empty list and single node carefully before moving on.

Think about cycles and shared random pointers that can cause infinite loops or duplicates.

Optimize your solution to O(n) time and O(1) or O(n) space to handle large inputs efficiently.

t1_01basic

Input{"head":[[7,null],[13,0],[11,4],[10,2],[1,0]]}

Expected[[7,null],[13,0],[11,4],[10,2],[1,0]]

⏱ Performance - must finish in 2000ms

The list has 5 nodes. Each node's random pointer points to the index given (or null). The output is a deep copy with the same structure and random pointers.

💡 Think about how to create a new node for each original node while preserving random pointers.

💡 Use a hash map to map original nodes to their copies to assign next and random pointers correctly.

💡 First create all new nodes without pointers, then assign next and random pointers using the map.

Why it failed: Returned list structure or random pointers do not match the original. Likely forgot to deep copy nodes or incorrectly assigned random pointers. Fix by mapping original nodes to new nodes and assigning pointers accordingly.

✓ Correct deep copy with all next and random pointers properly assigned.

t1_02basic

Input{"head":[[1,null],[2,0],[3,1]]}

Expected[[1,null],[2,0],[3,1]]

⏱ Performance - must finish in 2000ms

List of 3 nodes where random pointers form a chain back to previous nodes. The deep copy must replicate this structure exactly.

💡 Ensure that random pointers in the copied list point to the copied nodes, not the original nodes.

💡 Use a dictionary or map to keep track of original to copied node mappings.

💡 After creating all nodes, iterate again to assign next and random pointers using the map.

Why it failed: Random pointers in the copied list point to original nodes or are null incorrectly. Fix by using a mapping from original nodes to copied nodes when assigning random pointers.

✓ Random pointers correctly assigned to copied nodes, replicating original structure.

t2_01edge

Input{"head":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty list input should return null (empty list) as output.

💡 Check if the input head is null or empty before processing.

💡 Return null immediately if the list is empty to avoid errors.

💡 Add a base case to handle empty input at the start of your function.

Why it failed: Function crashes or returns non-null for empty input. Fix by adding a check for null or empty head and returning null immediately.

✓ Correctly returns null for empty input.

t2_02edge

Input{"head":[[42,0]]}

Expected[[42,0]]

⏱ Performance - must finish in 2000ms

Single node list where random pointer points to itself. The copy must replicate this self-referential random pointer.

💡 Handle the case where random pointer points to the node itself.

💡 Ensure the mapping correctly assigns the random pointer to the copied node, not original.

💡 When assigning random pointers, use the map to assign copied node's random to itself if original random points to itself.

Why it failed: Random pointer in copied node is null or points to original node. Fix by using the mapping to assign random pointers correctly, including self-pointing.

✓ Random pointer correctly points to the copied node itself.

t2_03edge

Input{"head":[[5,null],[6,null],[7,null]]}

Expected[[5,null],[6,null],[7,null]]

⏱ Performance - must finish in 2000ms

List with multiple nodes where all random pointers are null. The copy should have all random pointers null as well.

💡 Random pointers can be null; ensure your code handles this without errors.

💡 When assigning random pointers, check if original random is null before mapping.

💡 Assign null to copied node's random pointer if original random pointer is null.

Why it failed: Random pointers in copied list incorrectly assigned non-null values or cause errors. Fix by checking for null before assigning random pointers.

✓ All random pointers correctly assigned as null.

t2_04edge

Input{"head":[[1,2],[2,0],[3,1]]}

Expected[[1,2],[2,0],[3,1]]

⏱ Performance - must finish in 2000ms

Random pointers form a cycle: node0.random -> node2, node2.random -> node1, node1.random -> node0. Copy must replicate cycle without infinite loop.

💡 Beware of infinite loops when random pointers form cycles.

💡 Use a visited map or memoization to avoid revisiting nodes during copy.

💡 Implement iterative or memoized recursion with a map to handle cycles safely.

Why it failed: Function enters infinite recursion or loop due to cycles in random pointers. Fix by using a map to track visited nodes and avoid revisiting during copy.

✓ Cycles in random pointers handled correctly without infinite loops.

t3_01corner

Input{"head":[[10,1],[20,1],[30,1]]}

Expected[[10,1],[20,1],[30,1]]

⏱ Performance - must finish in 2000ms

All random pointers point to the same node (node1). Copy must replicate this shared random pointer correctly.

💡 Check that multiple nodes can share the same random pointer target.

💡 Use a single mapping for each original node to one copied node.

💡 Assign random pointers using the map to ensure shared references are preserved.

Why it failed: Random pointers in copy do not preserve shared references, resulting in multiple copies of the same node. Fix by mapping original nodes to single copied nodes and reusing them.

✓ Shared random pointers correctly preserved in the copy.

t3_02corner

Input{"head":[[1,0],[2,1],[3,2],[4,3],[5,4]]}

Expected[[1,0],[2,1],[3,2],[4,3],[5,4]]

⏱ Performance - must finish in 2000ms

Random pointers form a chain pointing to themselves or previous nodes. Copy must replicate exact structure.

💡 Ensure that random pointers can point backwards or to self.

💡 Use a map to assign random pointers after all nodes are copied.

💡 Do not assign random pointers during node creation; assign after all nodes exist.

Why it failed: Random pointers assigned before all nodes are copied, causing null or incorrect pointers. Fix by separating node creation and pointer assignment phases.

✓ Random pointers correctly assigned after all nodes are copied.

t3_03corner

Input{"head":[[1,2],[2,null],[3,0]]}

Expected[[1,2],[2,null],[3,0]]

⏱ Performance - must finish in 2000ms

Random pointers include null and cross references. Copy must replicate null and cross references correctly.

💡 Handle null random pointers correctly alongside non-null ones.

💡 Use a map to assign random pointers after all nodes are copied.

💡 Check for null before assigning random pointers to avoid errors.

Why it failed: Random pointers incorrectly assigned null or wrong nodes. Fix by checking null and using map for assignment.

✓ Random pointers correctly assigned including null and cross references.

t4_01performance

Input{"head":[[1,999],[2,0],[3,1],[4,2],[5,3],[6,4],[7,5],[8,6],[9,7],[10,8],[11,9],[12,10],[13,11],[14,12],[15,13],[16,14],[17,15],[18,16],[19,17],[20,18],[21,19],[22,20],[23,21],[24,22],[25,23],[26,24],[27,25],[28,26],[29,27],[30,28],[31,29],[32,30],[33,31],[34,32],[35,33],[36,34],[37,35],[38,36],[39,37],[40,38],[41,39],[42,40],[43,41],[44,42],[45,43],[46,44],[47,45],[48,46],[49,47],[50,48],[51,49],[52,50],[53,51],[54,52],[55,53],[56,54],[57,55],[58,56],[59,57],[60,58],[61,59],[62,60],[63,61],[64,62],[65,63],[66,64],[67,65],[68,66],[69,67],[70,68],[71,69],[72,70],[73,71],[74,72],[75,73],[76,74],[77,75],[78,76],[79,77],[80,78],[81,79],[82,80],[83,81],[84,82],[85,83],[86,84],[87,85],[88,86],[89,87],[90,88],[91,89],[92,90],[93,91],[94,92],[95,93],[96,94],[97,95],[98,96],[99,97],[100,98],[101,99],[102,100],[103,101],[104,102],[105,103],[106,104],[107,105],[108,106],[109,107],[110,108],[111,109],[112,110],[113,111],[114,112],[115,113],[116,114],[117,115],[118,116],[119,117],[120,118],[121,119],[122,120],[123,121],[124,122],[125,123],[126,124],[127,125],[128,126],[129,127],[130,128],[131,129],[132,130],[133,131],[134,132],[135,133],[136,134],[137,135],[138,136],[139,137],[140,138],[141,139],[142,140],[143,141],[144,142],[145,143],[146,144],[147,145],[148,146],[149,147],[150,148],[151,149],[152,150],[153,151],[154,152],[155,153],[156,154],[157,155],[158,156],[159,157],[160,158],[161,159],[162,160],[163,161],[164,162],[165,163],[166,164],[167,165],[168,166],[169,167],[170,168],[171,169],[172,170],[173,171],[174,172],[175,173],[176,174],[177,175],[178,176],[179,177],[180,178],[181,179],[182,180],[183,181],[184,182],[185,183],[186,184],[187,185],[188,186],[189,187],[190,188],[191,189],[192,190],[193,191],[194,192],[195,193],[196,194],[197,195],[198,196],[199,197],[200,198],[201,199],[202,200],[203,201],[204,202],[205,203],[206,204],[207,205],[208,206],[209,207],[210,208],[211,209],[212,210],[213,211],[214,212],[215,213],[216,214],[217,215],[218,216],[219,217],[220,218],[221,219],[222,220],[223,221],[224,222],[225,223],[226,224],[227,225],[228,226],[229,227],[230,228],[231,229],[232,230],[233,231],[234,232],[235,233],[236,234],[237,235],[238,236],[239,237],[240,238],[241,239],[242,240],[243,241],[244,242],[245,243],[246,244],[247,245],[248,246],[249,247],[250,248],[251,249],[252,250],[253,251],[254,252],[255,253],[256,254],[257,255],[258,256],[259,257],[260,258],[261,259],[262,260],[263,261],[264,262],[265,263],[266,264],[267,265],[268,266],[269,267],[270,268],[271,269],[272,270],[273,271],[274,272],[275,273],[276,274],[277,275],[278,276],[279,277],[280,278],[281,279],[282,280],[283,281],[284,282],[285,283],[286,284],[287,285],[288,286],[289,287],[290,288],[291,289],[292,290],[293,291],[294,292],[295,293],[296,294],[297,295],[298,296],[299,297],[300,298],[301,299],[302,300],[303,301],[304,302],[305,303],[306,304],[307,305],[308,306],[309,307],[310,308],[311,309],[312,310],[313,311],[314,312],[315,313],[316,314],[317,315],[318,316],[319,317],[320,318],[321,319],[322,320],[323,321],[324,322],[325,323],[326,324],[327,325],[328,326],[329,327],[330,328],[331,329],[332,330],[333,331],[334,332],[335,333],[336,334],[337,335],[338,336],[339,337],[340,338],[341,339],[342,340],[343,341],[344,342],[345,343],[346,344],[347,345],[348,346],[349,347],[350,348],[351,349],[352,350],[353,351],[354,352],[355,353],[356,354],[357,355],[358,356],[359,357],[360,358],[361,359],[362,360],[363,361],[364,362],[365,363],[366,364],[367,365],[368,366],[369,367],[370,368],[371,369],[372,370],[373,371],[374,372],[375,373],[376,374],[377,375],[378,376],[379,377],[380,378],[381,379],[382,380],[383,381],[384,382],[385,383],[386,384],[387,385],[388,386],[389,387],[390,388],[391,389],[392,390],[393,391],[394,392],[395,393],[396,394],[397,395],[398,396],[399,397],[400,398],[401,399],[402,400],[403,401],[404,402],[405,403],[406,404],[407,405],[408,406],[409,407],[410,408],[411,409],[412,410],[413,411],[414,412],[415,413],[416,414],[417,415],[418,416],[419,417],[420,418],[421,419],[422,420],[423,421],[424,422],[425,423],[426,424],[427,425],[428,426],[429,427],[430,428],[431,429],[432,430],[433,431],[434,432],[435,433],[436,434],[437,435],[438,436],[439,437],[440,438],[441,439],[442,440],[443,441],[444,442],[445,443],[446,444],[447,445],[448,446],[449,447],[450,448],[451,449],[452,450],[453,451],[454,452],[455,453],[456,454],[457,455],[458,456],[459,457],[460,458],[461,459],[462,460],[463,461],[464,462],[465,463],[466,464],[467,465],[468,466],[469,467],[470,468],[471,469],[472,470],[473,471],[474,472],[475,473],[476,474],[477,475],[478,476],[479,477],[480,478],[481,479],[482,480],[483,481],[484,482],[485,483],[486,484],[487,485],[488,486],[489,487],[490,488],[491,489],[492,490],[493,491],[494,492],[495,493],[496,494],[497,495],[498,496],[499,497],[500,498],[501,499],[502,500],[503,501],[504,502],[505,503],[506,504],[507,505],[508,506],[509,507],[510,508],[511,509],[512,510],[513,511],[514,512],[515,513],[516,514],[517,515],[518,516],[519,517],[520,518],[521,519],[522,520],[523,521],[524,522],[525,523],[526,524],[527,525],[528,526],[529,527],[530,528],[531,529],[532,530],[533,531],[534,532],[535,533],[536,534],[537,535],[538,536],[539,537],[540,538],[541,539],[542,540],[543,541],[544,542],[545,543],[546,544],[547,545],[548,546],[549,547],[550,548],[551,549],[552,550],[553,551],[554,552],[555,553],[556,554],[557,555],[558,556],[559,557],[560,558],[561,559],[562,560],[563,561],[564,562],[565,563],[566,564],[567,565],[568,566],[569,567],[570,568],[571,569],[572,570],[573,571],[574,572],[575,573],[576,574],[577,575],[578,576],[579,577],[580,578],[581,579],[582,580],[583,581],[584,582],[585,583],[586,584],[587,585],[588,586],[589,587],[590,588],[591,589],[592,590],[593,591],[594,592],[595,593],[596,594],[597,595],[598,596],[599,597],[600,598],[601,599],[602,600],[603,601],[604,602],[605,603],[606,604],[607,605],[608,606],[609,607],[610,608],[611,609],[612,610],[613,611],[614,612],[615,613],[616,614],[617,615],[618,616],[619,617],[620,618],[621,619],[622,620],[623,621],[624,622],[625,623],[626,624],[627,625],[628,626],[629,627],[630,628],[631,629],[632,630],[633,631],[634,632],[635,633],[636,634],[637,635],[638,636],[639,637],[640,638],[641,639],[642,640],[643,641],[644,642],[645,643],[646,644],[647,645],[648,646],[649,647],[650,648],[651,649],[652,650],[653,651],[654,652],[655,653],[656,654],[657,655],[658,656],[659,657],[660,658],[661,659],[662,660],[663,661],[664,662],[665,663],[666,664],[667,665],[668,666],[669,667],[670,668],[671,669],[672,670],[673,671],[674,672],[675,673],[676,674],[677,675],[678,676],[679,677],[680,678],[681,679],[682,680],[683,681],[684,682],[685,683],[686,684],[687,685],[688,686],[689,687],[690,688],[691,689],[692,690],[693,691],[694,692],[695,693],[696,694],[697,695],[698,696],[699,697],[700,698],[701,699],[702,700],[703,701],[704,702],[705,703],[706,704],[707,705],[708,706],[709,707],[710,708],[711,709],[712,710],[713,711],[714,712],[715,713],[716,714],[717,715],[718,716],[719,717],[720,718],[721,719],[722,720],[723,721],[724,722],[725,723],[726,724],[727,725],[728,726],[729,727],[730,728],[731,729],[732,730],[733,731],[734,732],[735,733],[736,734],[737,735],[738,736],[739,737],[740,738],[741,739],[742,740],[743,741],[744,742],[745,743],[746,744],[747,745],[748,746],[749,747],[750,748],[751,749],[752,750],[753,751],[754,752],[755,753],[756,754],[757,755],[758,756],[759,757],[760,758],[761,759],[762,760],[763,761],[764,762],[765,763],[766,764],[767,765],[768,766],[769,767],[770,768],[771,769],[772,770],[773,771],[774,772],[775,773],[776,774],[777,775],[778,776],[779,777],[780,778],[781,779],[782,780],[783,781],[784,782],[785,783],[786,784],[787,785],[788,786],[789,787],[790,788],[791,789],[792,790],[793,791],[794,792],[795,793],[796,794],[797,795],[798,796],[799,797],[800,798],[801,799],[802,800],[803,801],[804,802],[805,803],[806,804],[807,805],[808,806],[809,807],[810,808],[811,809],[812,810],[813,811],[814,812],[815,813],[816,814],[817,815],[818,816],[819,817],[820,818],[821,819],[822,820],[823,821],[824,822],[825,823],[826,824],[827,825],[828,826],[829,827],[830,828],[831,829],[832,830],[833,831],[834,832],[835,833],[836,834],[837,835],[838,836],[839,837],[840,838],[841,839],[842,840],[843,841],[844,842],[845,843],[846,844],[847,845],[848,846],[849,847],[850,848],[851,849],[852,850],[853,851],[854,852],[855,853],[856,854],[857,855],[858,856],[859,857],[860,858],[861,859],[862,860],[863,861],[864,862],[865,863],[866,864],[867,865],[868,866],[869,867],[870,868],[871,869],[872,870],[873,871],[874,872],[875,873],[876,874],[877,875],[878,876],[879,877],[880,878],[881,879],[882,880],[883,881],[884,882],[885,883],[886,884],[887,885],[888,886],[889,887],[890,888],[891,889],[892,890],[893,891],[894,892],[895,893],[896,894],[897,895],[898,896],[899,897],[900,898],[901,899],[902,900],[903,901],[904,902],[905,903],[906,904],[907,905],[908,906],[909,907],[910,908],[911,909],[912,910],[913,911],[914,912],[915,913],[916,914],[917,915],[918,916],[919,917],[920,918],[921,919],[922,920],[923,921],[924,922],[925,923],[926,924],[927,925],[928,926],[929,927],[930,928],[931,929],[932,930],[933,931],[934,932],[935,933],[936,934],[937,935],[938,936],[939,937],[940,938],[941,939],[942,940],[943,941],[944,942],[945,943],[946,944],[947,945],[948,946],[949,947],[950,948],[951,949],[952,950],[953,951],[954,952],[955,953],[956,954],[957,955],[958,956],[959,957],[960,958],[961,959],[962,960],[963,961],[964,962],[965,963],[966,964],[967,965],[968,966],[969,967],[970,968],[971,969],[972,970],[973,971],[974,972],[975,973],[976,974],[977,975],[978,976],[979,977],[980,978],[981,979],[982,980],[983,981],[984,982],[985,983],[986,984],[987,985],[988,986],[989,987],[990,988],[991,989],[992,990],[993,991],[994,992],[995,993],[996,994],[997,995],[998,996],[999,997],[1000,998]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large list with 1000 nodes and random pointers forming a cycle. Must complete in O(n) time within 2 seconds.

💡 Use O(n) time and O(n) space approach with a hash map or O(1) space approach with node weaving.

💡 Avoid recursive solutions that may cause stack overflow or exponential time.

💡 Iterate the list multiple times to create copies, assign next and random pointers efficiently.

Why it failed: Solution times out due to exponential or quadratic complexity. Fix by implementing O(n) time solution using hash map or weaving technique.

✓ Solution runs within time limit confirming O(n) complexity.

Practice

1. Consider the following partial Skiplist search method code. After inserting values 1, 3, and 7, what will be the value of curr.val after the outer loop finishes when searching for target = 3?

easy

A. 7

B. 1

C. 3

D. -1

Solution

1. Step 1: Trace outer loop from highest to lowest level

   At each level, move forward while next node's value is less than 3. After finishing, curr points to node with value just less than or equal to 3.

2. Step 2: Move curr to forward[0]

   After the loop, curr moves to forward[0], which should be node with value 3 if it exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Search finds node with value 3 exactly [OK]

Hint: Search stops at node before target, then moves forward once [OK]

Common Mistakes:

• Off-by-one error in loop
• Confusing curr position before and after loop
• Assuming curr stays at head

2. You need to design a system that stores a fixed number of key-value pairs and supports fast retrieval and insertion. When the capacity is exceeded, the system must evict the least recently accessed item. Which data structure approach best guarantees O(1) time complexity for both retrieval and insertion while maintaining the eviction policy?

easy

A. Use a simple list to store keys in order of usage and a hash map for key-value pairs.

B. Use a queue to store keys and a hash map for values.

C. Use a hash map combined with a doubly linked list to track usage order.

D. Use a balanced binary search tree keyed by access timestamps.

Solution

1. Step 1: Understand the eviction policy

   The system must evict the least recently accessed item, which requires tracking usage order efficiently.

2. Step 2: Identify data structure supporting O(1) operations

   A hash map provides O(1) access to values, and a doubly linked list allows O(1) updates to usage order by moving nodes.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map + doubly linked list is the classic LRU cache design [OK]

Hint: LRU needs O(1) access and update of usage order [OK]

Common Mistakes:

• Using list causes O(n) removal
• Queue can't reorder on access
• BST adds O(log n) overhead

3. Suppose the AllOne data structure is extended to allow keys to be reused after removal (i.e., keys can be reinserted after their count reaches zero). Which modification is necessary to maintain O(1) operations and correctness?

hard

A. Do nothing special; existing code handles reuse correctly

B. Maintain a separate reuse queue to track keys that can be reinserted

C. Reset key's count to zero and keep it in the data structure to track reuse

D. Ensure keys are fully removed from all buckets and mappings upon count zero, then treat reuse as new insertion

Solution

1. Step 1: Understand reuse implications

   Keys removed at count zero must be fully deleted to avoid stale references.

2. Step 2: Ensure reuse is treated as new insertion

   On reuse, key is inserted fresh with count 1, requiring clean removal previously.

3. Step 3: Confirm O(1) operations

   Full removal and fresh insertion maintain O(1) updates and correctness.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Proper removal prevents duplicates and stale buckets [OK]

Hint: Full removal before reuse ensures correctness and O(1) ops [OK]

Common Mistakes:

• Keeping keys with zero count in data structure causes bugs

4. Suppose the stack is modified to allow reusing popped elements by pushing them back later, and the increment operation must still work correctly. Which modification to the optimal lazy increment approach is necessary to maintain correctness?

hard

A. Store increments per element rather than per index, requiring a more complex data structure.

B. Reset the entire increments array to zero on each push to avoid stale increments.

C. Track increments with a stack of (index, increment) pairs and apply them on pop accordingly.

D. No change needed; the existing lazy increment array works correctly with reused elements.

Solution

1. Step 1: Understand reuse impact

   Reusing popped elements means the same stack positions may hold different elements over time, so increments per index become invalid.

2. Step 2: Modify increment tracking

   To maintain correctness, increments must be tracked per element, not per index, requiring a data structure that associates increments with elements themselves.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Per-element increments prevent stale increment application on reused positions [OK]

Hint: Reusing elements breaks index-based increments; track per element [OK]

Common Mistakes:

• Assuming no change needed
• Resetting increments array loses valid increments

5. Suppose the data stream allows duplicate numbers to be removed after insertion, requiring support for removeNum(num). Which modification to the balanced two heaps approach is necessary to maintain correct median retrieval?

hard

A. Use a balanced binary search tree instead of heaps to allow efficient removals.

B. Ignore removals and only add numbers, as removals break the heap structure.

C. Rebuild both heaps from scratch after every removal to maintain heap properties.

D. Add a delayed deletion map to mark elements for lazy removal and prune heaps during addNum and findMedian.

Solution

1. Step 1: Understand removal challenges

   Heaps do not support efficient arbitrary removals, so direct removal breaks heap properties.

2. Step 2: Use lazy deletion

   Maintain a delayed deletion map to mark elements for removal and prune them lazily during heap operations, preserving heap structure and efficiency.

3. Step 3: Avoid costly rebuilds

   Rebuilding heaps on every removal is inefficient; ignoring removals is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Lazy deletion with pruning maintains correctness and efficiency [OK]

Hint: Lazy deletion map enables efficient removals in heaps [OK]

Common Mistakes:

• Rebuilding heaps on every removal
• Ignoring removals breaks correctness