Leetcode-Data Structure

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

  1. choose an appropriate data structure for the problems that you face in the interview
  2. 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:

  1. 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.
  2. It has O(1) time to efficiently retrieve smallest or largest element / check the topmost element of priority queue or min-heap. ➪ ✨
  3. 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
summary
  • Array
  1. 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]
  2. It has constant-time access element given the index, in O(1) time.

For the problem, I use this data structure:

  • Linked-list
  1. Compared to Array, delete and insert element takes O(1) but access element/search in O(n)
  2. Deque is doubly linked list. Insert left/right takes O(1) and Delete left/right takes O(1).
copied from [4]

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:

  1. A Dictionary/Hash map is a generalized array that consists of key-value-pairs. [1]
  2. It has constant-time access value given the key, in O(1) time, on average (without collision happening). [1]
  3. Hashing to get a key and Deleting key in O(1) time. [3]
  4. On average, Dictionary/Hash map can do insert, search, delete in O(1).

Application:

  1. find duplicated element in the array
  2. Search if object exists in the array already in O(1), compared to search on the array, O(n).
  3. Map object into unique id in O(1).
  4. 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:

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

https://github.com/aforarup/interview/blob/master/Data%20Structures%20and%20Algorithm/Algorithm%20Books/The%20Algorithm%20Design%20Manual%20by%20Steven%20S.%20Skiena.pdf

[4].https://github.com/Si29io/course-note/blob/master/si29-course-note.md

I’m Taiwanese expat. I’v worked in Singapore as data scientist after graduation from Taiwan and currently I work in Amsterdam as machine learning engineer.