Data Structures and Algorithms problems is a world of static arrays, pointers, queues, stacks and binary trees. Many people starting out with DSA are using Python which is a high-level, loosely typed language that is not designed for low-level operations.
So inherently, DSA and Python are at odds with one another. We need to solve low-level problems but we have to use a high-level language. This can be frustrating, but with the right approach we can use this contradiction to our advantage.
Let’s draw a distinction in problem design. There’s is a particular data structure like a static array. And then there is the implementation of the algorithm. With Python we find that we will use List and Dict types for implementing just about every data structure and algorithm type. So how do we create leverage in this situation.
The trick is knowing the built-in methods for list and dict types. Once we we map out our solution using pseudo code and built in Python methods like .count(), .insert(), .index() from there implementing a pointer driven solution is a breeze.
Below is a table of Python list methods. These high level methods save us writing a lot of for/while loops which makes it easy to go from a pseudo code solution to a high-level code implementation.
- append() Adds an element at the end of the list
- clear() Removes all the elements from the list
- copy() Returns a copy of the list
- count() Returns the number of elements with the specified value
- extend() Add the elements of a list (or any iterable), to the end of the current list
- index() Returns the index of the first element with the specified value
- insert() Adds an element at the specified position
- pop() Removes the element at the specified position
- remove() Removes the first item with the specified value
- reverse() Reverses the order of the list
- sort() Sorts the list
Let’s use the methods above to solve a classic static array problem — moving all occurrences of a specific value to the end of the array in-place (without the use of a temporary list/variable). In this example we will move all occurrences of number 4 to the end of the array which is implemented as a list. We will store our unsorted array in a variable arr and number 4 in the variable val.
1 — count the number of value occurrences in the list (the value appears n-times)
2 — remove the value, and insert it at the end of the array
3 — repeat the above step 2 n times
In the solution above we use the .count list method to find how many times 4 occurs in the unsorted list. We use a while loop to limit the number of times remove and insert operations are performed. Python list remove method removes the first occurrence of the value. Inserting the same value at len(arr) index saves us from writing complex index pointer tracking code.
Thus, we have a solution in Python that closely mirrors our pseudo code. From here we can implement each Python list method as it’s own for/while loop if that is required by the problem.