In-place [mp]

Micro pattern¶

Description¶

Reuse an input structure for output, metadata, or rearrangement instead of allocating an equivalent auxiliary structure.

Problems¶

Arrays and matrices¶

Overwrite, swap, transpose, reverse, or partition elements in the input container.

• Bubble sort (DSA)
• Quick sort (DSA)
• Heap sort (DSA)
• Shell sort (DSA)
• Insertion sort (DSA)
• Selection sort (DSA)
• Bottom-up merge sort (DSA)
• Top-down merge sort (DSA)
• 26. Remove Duplicates from Sorted Array (Top Easy)
• 48. Rotate Image (Top Easy)
• 75. Sort Colors (Top Medium)
• 88. Merge Sorted Array (Top Easy)
• 189. Rotate Array (Top Easy)
• 283. Move Zeroes (Top Easy)
• 344. Reverse String (Top Easy)
• 384. Shuffle an Array (Top Easy)
• 289. Game of Life (Top Hard)
• 41. First Missing Positive (Top Hard)

Linked lists¶

Rewire existing nodes instead of representing the list with copied values.

• Insertion sort linked list (DSA)
• Bottom-up merge sort linked list (DSA)
• Top-down merge sort linked list (DSA)
• 206. Reverse Linked List (Top Easy)
• 234. Palindrome Linked List (Top Easy)
• 328. Odd Even Linked List (Top Medium)
• 138. Copy List with Random Pointer (Top Hard)
• 148. Sort List (Top Hard)

Trees¶

Reuse existing pointers to traverse and link tree levels.

• 116. Populating Next Right Pointers in Each Node (Top Medium)
• 669. Trim a Binary Search Tree (Google Prep)

In-place marking¶

Overwrite cells temporarily or permanently to encode visitation or metadata.

• 73. Set Matrix Zeroes (Top Medium)
• 79. Word Search (Top Medium)
• 200. Number of Islands (Top Medium)
• 130. Surrounded Regions (Top Hard)
• 212. Word Search II (Top Hard)
• 1926. Nearest Exit from Entrance in Maze (Graph Theory)
• 934. Shortest Bridge (Graph Theory)
• 1091. Shortest Path in Binary Matrix (Graph Theory)
• 1020. Number of Enclaves (Graph Theory)
• 1254. Number of Closed Islands (Graph Theory)
• 695. Max Area of Island (Graph Theory)