Arrays ​

Python ​

Implemented as type list in Python (both a vector and an array)

Rust ​

Use Vec<T> for a vector. Use [T] for an array, e.g., let a = [0_f32; 64]; will create an array of 64 floating point zeros. - Be aware of the differences between using .iter() and .into_iter(). See Essential Rust Syntax Explained.

Essential Operations ​

Basics. Basic array-style operations are conducted via

• .len() - Gets the length of the vector
• .push(x) - Appends an element to the back of the vector
• .pop() - Removes an element from the back of the vector, returns it
• .append(other) - Extends/concatenates the two vectors together
• .insert(i, x) - Inserts x at index i (operation shifts remaining elements right)
• .remove(i) Removes the element at i (operation shifts remaining elements left)
• .contains(x) - True if the vector contains x (operation is $O(n)$)
• .join(x) - Joins the elements given the same type x
• .get(x) - Gets a reference to an element or sub-slice
• .sort() - Sorts the elements in $O(n \text{ log } n)$ time.

Replace value in-place. Removing and inserting from an array is wasteful because all of the elements have to be shifted. Instead, use std::mem::replace, or access it directly (not recommended).

let mut v = vec![1, 2, 3, 4];
let got = std::mem::replace(&mut v[2], 42); // -> [1, 2, 42, 4], got = 3
// OR replace directly, but will panic out of bounds
v[1] = 56; // -> [1, 56, 42, 4]

let mut v = vec![1, 2, 3, 4];
let got = std::mem::replace(&mut v[2], 42); // -> [1, 2, 42, 4], got = 3
// OR replace directly, but will panic out of bounds
v[1] = 56; // -> [1, 56, 42, 4]

Looping. When looping over a vector you must use either .into_iter() or .iter(). The following code doesn't compile because v is consumed by into_iter(), and therefore cannot be used with iter() later without a clone().

let v = vec![1, 2, 3, 4, 5];
// `into_iter()` consumes the original vector returning an owned variable
// `iter()` returns a reference to each variable
for x in v.into_iter() { ... } // => i32 
for x in v.iter() { ... }      // => &i32 notice this is a reference

let v = vec![1, 2, 3, 4, 5];
// `into_iter()` consumes the original vector returning an owned variable
// `iter()` returns a reference to each variable
for x in v.into_iter() { ... } // => i32 
for x in v.iter() { ... }      // => &i32 notice this is a reference

Filtering. Use .filter() or .retain() to remove values from the vector.

let nums: Vec<i32> = vec![3, 1, 3, 4, 4, 55, 4, 66];

let filt: Vec<i32> = nums.into_iter().filter(|&x| x < 10).collect();
let filt: Vec<&i32> = nums.iter().filter(|&x| *x < 10).collect();
// OR use in-place methods
let mut nums: Vec<i32> = vec![3, 1, 3, 4, 4, 55, 4, 66];
nums.retain(|&x| x < 10);

let nums: Vec<i32> = vec![3, 1, 3, 4, 4, 55, 4, 66];

let filt: Vec<i32> = nums.into_iter().filter(|&x| x < 10).collect();
let filt: Vec<&i32> = nums.iter().filter(|&x| *x < 10).collect();
// OR use in-place methods
let mut nums: Vec<i32> = vec![3, 1, 3, 4, 4, 55, 4, 66];
nums.retain(|&x| x < 10);

Removing duplicates.

// Option 1: Sort O(n log n) and deduplicate O(n)
let mut nums: Vec<i32> = vec![3, 1, 3, 4, 4, 55, 4, 66];
nums.sort();
nums.dedup();

// Option 2: Convert to set and back to vector
let mut nums: Vec<i32> = vec![3, 1, 3, 4, 4, 55, 4, 66];
let set: HashSet<i32> = nums.into_iter().collect();
let vec: Vec<i32> = set.into_iter().collect();

// Option 1: Sort O(n log n) and deduplicate O(n)
let mut nums: Vec<i32> = vec![3, 1, 3, 4, 4, 55, 4, 66];
nums.sort();
nums.dedup();

// Option 2: Convert to set and back to vector
let mut nums: Vec<i32> = vec![3, 1, 3, 4, 4, 55, 4, 66];
let set: HashSet<i32> = nums.into_iter().collect();
let vec: Vec<i32> = set.into_iter().collect();

Problems ​

5.1 Dutch National Flag Problem ​

I successfully found the brute force solution. The trick that I missed on this question was that I only used two pointers, but three pointers were needed into the array. One for lesser, one for equal, and one for larger. I also ran into the difficulty that I didn't look ahead to how the sorting would resolve itself, but instead presumed that it would have to be sorted on the initial switch. This caused a complicated if-elif-else block to try and handle everything.

To solve this problem you can either use two passes, with two pointers each time. On the first pass, keep track of the left-most element larger than the pivot, and then move an index pointer to the right until you find an element smaller than the pivot, then switch them. It's okay that you'll have pivot values interspersed with larger values, because you do another pass. On the second pass, loop through from the right, keeping track of the rightmost value equal to the pivot, then move an index pointer until you find one larger than the pivot, swap them, and increment the pivot-equal index pointer.

The one-pass solution requires three pointers as mentioned above, and you combine the above two-pass solution into an if-block on each iteration that has three cases. Smaller, equal (then increment) or larger, if not equal, swap them.

5.2 Increment integer array ​

Got this one, fast version, first try, good work!

5.6 Buy and sell a stock once OR LC 121 Best time to buy and sell stock ​

Solution: Create variables for the max difference and current min. With a single iteration conduct the following steps, (i) update the current difference and update the max difference if it is larger, (ii) update the min price if the current price is lower. This problem can be solved in $O(n)$ time and $O(1)$ additional space.

Trick: Focus on the minimum price and the maximum difference, not the global max and min values---the target max may not be the global max. You cannot focus on the global max and min values directly because there is an intrinsic ordering that needs to be accounted for, e.g. the stock needs to be bought at a min prior to selling at a max. If you only keep track of the max and min values, then it's difficult to ensure that the min comes before the max.

Alternative: This problem can also be solved with a two-pointer approach whereby the right pointer moves faster than the left pointer and searches for maximums and the left pointer remains at the current global minimum.

5.12 Sample random data ​

5.17 Sudoku checker problem ​

When indexing a native Python 2D array X[i][j] accesses the ith row at the jth column

5.18 Spiral ordering of a 2D array ​

Did this one correctly with NumPy (after some time though), the difficultly wasn't particularly the solution, but instead it was coding it correctly. Author recommends taking only n-1 for each spiralled row/column.

• Useful tools:
  • filter to remove all the zeros
  • set to remove duplicates, and check if equal to the length of list prior

LC 11 Container with Most Water ​

My first solution (C++) wasn't quite right. I implemented the pseudocode correctly, but my approach failed to search all possible combinations.

I did use an array-based approach, this is good. I also used a two-pointer approach, as is recommended for the best solution. However, I started both pointers at the left-most index. I should've noted that I should put the pointers at the left-most and right-most placements (as far apart as possible), and slowly move them together, calculating if any new areas are larger than the current max area.

Rust solution

use std::cmp::{min, max};

impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let mut li = 0;
        let mut ri = height.len() - 1;
        let mut max_area = 0;
        let mut curr_area = 0;
        while li < ri {
            // Be aware of the usize and i32 casting required here
            curr_area = min(height[li], height[ri]) * (li as i32 - ri as i32).abs();
            max_area = max(max_area, curr_area);

            if height[li] < height[ri] {
                li = li + 1;
            } else {
                ri = ri - 1;
            }
        }
        max_area as i32
    }
}

use std::cmp::{min, max};

impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let mut li = 0;
        let mut ri = height.len() - 1;
        let mut max_area = 0;
        let mut curr_area = 0;
        while li < ri {
            // Be aware of the usize and i32 casting required here
            curr_area = min(height[li], height[ri]) * (li as i32 - ri as i32).abs();
            max_area = max(max_area, curr_area);

            if height[li] < height[ri] {
                li = li + 1;
            } else {
                ri = ri - 1;
            }
        }
        max_area as i32
    }
}

LC 21 Merge Two Sorted Lists ​

Solution: Start by creating an output linked list with curr = dummy_head = ListNode() and conduct all further operations on curr. Loop over both input lists until one is exhausted (using a while loop with an AND operator) to update curr according to whether the head of list1 or list2 is smaller. Linked list operations including append and move are required here. Once one of the lists is exhausted append the remaining head to curr to complete the list. Finally, return dummy_head.next to mark the head of the resulting linked list (since curr now points to the tail).

• One loop => time complexity of $O(n)$
• Output linked list => space complexity of $O(n)$ with no additional space complexity besides the output

Alternative (not recommended): Before conducting the while loop, iterative over both input lists and determine which one has that largest tail, then swap accordingly such that list1 will always be exhausted first. This removes the need to use an AND operator in the while condition, but adds additional null case conditions and runtime overhead (due to extra iterations). Time and space complexities remain the same.

LC 125 Valid Palindrome ​

Solution: Use a two tracker approach initializing the index trackers with left, right = 0, len(s) - 1. Create an alphanumeric lookup with alphanumeric = set("abcdefghijklmnopqrstuvwxyz0123456789"). Set the string to lowercase. Finally, loop over the string while left < right. At each iteration check that the characters pointed to by the left and right trackers are alphanumeric, if not, increment the appropriate tracker and continue. If both characters are alpha numeric, check if they're different, if they are then it's not a palindrome and return False. At the end of the loop, return True.

LC 733 Flood Fill ​

Solution: This is sort of an array and sort of a graph search problem. Do DFS given the starting point, make sure to establish variables for visited nodes and the starting_color so you know which elements to ignore when you traverse into them.

Trick: Ensure that you evaluate conditionals for grid bounds. The trick to this problem is more so clean coding than conceptual difficulty, that doesn't mean it's dead-beat simple however.

LC 169 Majority Element ​

Solution 1: Sorting. Sort the array and return the element in the middle.

• Time complexity $O(n \text{ log } n)$
• Space complexity O(1)

Solution 2: Hash table. Populate a hash table with the frequencies of the elements and then return the key that matches the maximum value.

• Time complexity O(n + w) from two passes, one to populate the hash table O(n) and one to get the max key O(w) where w is the number of unique entries.
• Space complexity O(w) for the hash table

Solution 3: Moore's voting algorithm. See here for a full explanation. This involves an iterative increment and decrement approach whereby the majority element always becomes the final candidate. Start with a count and candidate. On each iteration, if count == 0, make the the new candidate and increment, if the current value doesn't equal the candidate, decrement the count. If the current value does match the candidate, increment the count. In the end the candidate will be correct. Keep these sorts of incremenet/decrement algorithms in mind as they sometimes crop up.

LC 53 Maximum Subarray ​

This question tests your ability to identify either a dynamic programming approach, or a very specific algorithmic approach to the problem.

Solution 1: Kadane's algorithm. Establish max_sum = float('-inf') and current_sum = 0 variables. Loop over the array, on each iteration update the current sum, if the current sum is greater than the max sum, update the max sum. If at any time the current sum becomes negative, then set the current sum to 0—the most recently seen elements are reducing the current sum and cannot be contained within the maximum subarray.

Solution 2: Dynamic programming. Here, the key to the divide and conquer approach is to hold the largest sum of the elements already seen, and compare that to the current element. Is the largest sum already seen, plus the current element larger than the current element alone? Update to whichever is larger, and if the new largest sum is the globally largest, update the outer variable max_sum.

LC 57 Insert Interval ​

This problem tests your ability to merge overlapping intervals and manage complex insertion orders.

Solution: Create a result = [] to store the output. Loop over the intervals, if the interval is before the new interval, append it to result, if it's within the interval, take the max and min of the current bounds to 'stretch' the new interval. If the interval is after the new interval (non-overlapping) then append the new interval, and update the new interval to the current interval. Since subsequent intervals are guaranteed not to overlap, each new interval will be appended correctly.

LC 542 01 Matrix ​

This questions tests your understanding of grid traversal and multi-source BFS traversal. See this solution to the problem.

...redo...

Trick: Recognizing that this is a BFS problem is essential. DFS can be used for the similar LC 733 Flood Fill problem, however, you will run into issues regarding how each grid square is approached, e.g., if you approach a 1 through three previous 1's, you might set that square to 3 even though it's surrounded on 3 sides by 0s.

LC 15 Three Sum ​

This question tests your ability to recognize that, if you fix one value, it becomes the classic Two Sum problem. There are additional complexities to this problem. On LeetCode you need to solve it in a specific way or else you'll receive a timeout error, even if the complexity is $O(n^2)$ as per the recommended solution.

Solution: Sort the array. Next implement a two-pointer algorithm where you fix each entry one (resulting in $O(n^2)$ time complexity). Starting from either end, if you find that the resulting sum is negative, move the left pointer up (to increase the total sum) or if it's positive, move the right pointer down (to reduce the total sum).

Trick 1: Sort the array.