Data structure is a way to store data in the memory of computer. [1] Each data structure has its own advantages and disadvantages. So, the most important thing is to
- choose an appropriate data structure for the problems that you face in the interview
- know which operations are efficient in the chosen data structure.
What we should keep in mind when using a data structure to solve problem:
1. Why do we choose this DS in this problem? (Purpose)
2. How do we operate this DS in this problem? (Operation)
The below are some good-to-know data structure used to solve leetcode problem:
- Priority Queue or Min-Heap
Properties:
- It’s a data structure that make use of special key (usually designated to a certain value of input of problem) to quantify its priority and has O(log n) time for insertion and extraction/removal of element.
- It has O(1) time to efficiently retrieve smallest or largest element / check the topmost element of priority queue or min-heap. ➪ ✨
- In python3, the
heapqmodule provides an implementation of priority queue algorithm, which is min-heap by-default [2].
Application:
- Dijkstra’s algorithm
- Prim’s algorithm
For the problem, I use this data structure:
- 215. Kth Largest Element in an Array
- 253. Meeting Rooms II
- 373. Find K Pairs with Smallest Sums
- 347. Top K Frequent Elements
- 218. The Skyline Problem
- 23. Merge k Sorted Lists
- 295. Find Median from Data Stream
- 378. Kth Smallest Element in a Sorted Matrix
- Array
- It’s a fundamental contiguously-allocated data structure with fixed-size data records such that each element can be efficiently located by its index. [3]
- It has constant-time access element given the index, in O(1) time.
For the problem, I use this data structure:
- Linked-list
- Compared to Array, delete and insert element takes O(1) but access element/search in O(n)
- Deque is doubly linked list. Insert left/right takes O(1) and Delete left/right takes O(1).
For the problem, I use this data structure:
- 2. Add Two Numbers
- 24. Swap Nodes in Pairs
- 876. Middle of the Linked List
- 83. Remove Duplicates from Sorted List
- 61. Rotate List
- 86. Partition List
- 206. Reverse Linked List
- 92. Reverse Linked List II
- 141. Linked List Cycle
- 142. Linked List Cycle II
- 19. Remove Nth Node From End of List
- 203. Remove Linked List Elements
- 83. Remove Duplicates from Sorted List
- 82. Remove Duplicates from Sorted List II
- 237. Delete Node in a Linked List
- 369. Plus One Linked List
- 328. Odd Even Linked List
- 21. Merge Two Sorted Lists
- 23. Merge k Sorted Lists
- Dictionary/Hash map
Properties:
- A Dictionary/Hash map is a generalized array that consists of key-value-pairs. [1]
- It has constant-time access value given the key, in O(1) time, on average (without collision happening). [1]
- Hashing to get a key and Deleting key in O(1) time. [3]
- On average, Dictionary/Hash map can do insert, search, delete in O(1).
Application:
- find duplicated element in the array
- Search if object exists in the array already in O(1), compared to search on the array, O(n).
- Map object into unique id in O(1).
- when question mentioned to return maximum frequency or minimum frequency of something, use hashmap to store frequency of each something called count by convention.
For the problem, I use this data structure:
- 685. Redundant Connection II
- 737. Sentence Similarity II
- 734. Sentence Similarity
- 508. Most Frequent Subtree Sum
Reference:
[1]. Chapter 4, Competitive programmer handbook https://github.com/abhishekgahlot/competitive-progrmmer-handbook-python
[2]. https://docs.python.org/3/library/heapq.html
[3]. Chapter3, The algorithm design manual, 2nd edition
[4].https://github.com/Si29io/course-note/blob/master/si29-course-note.md
