Category Archives: Arrays

Arrays, Interview Questions

Max Consecutive Ones (Leetcode)

I think this is an interesting loop, and a nice intro question to people still getting their feet wet with programming and algorithmic thinking. It’s a sort of scan problem.

Solution

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        m = 0
        c = 0
        for n in nums:
            if n == 1:
                c += 1
                m = max(m, c)
            else:
                c = 0
        return m

The sort of “invariants” you have to maintain, or the general idea of the state-of-our-scanner (slightly) evolving as we see different values, is a good muscle to build.

More interesting loops here.

Arrays, Interview Questions

Intersection of Two Arrays (Leetcode)

Another from the archives. This is actually something I like as an interview question, so I suppose maybe that means I should change my interview question. I suppose candidates need to know what a set is, but given the domains I work in I think that’s a fair requirement. This question is to take two arrays of integers, and return their set-intersection.

I think a very reasonable approach is to immediately sort the input. After that, as we build the result vector, we can think about the invariants that are maintained: the result vector is in sorted order, and so the “unique-ification” we need to do can follow naturally from that.

Nevermind also the invariants that guide the overall merge-sort-esque loop iterations. We can reason about how we make forward progress.

Code Solution

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(begin(nums1), end(nums1));
        sort(begin(nums2), end(nums2));
        vector<int> result;
        
        int i = 0;
        int j = 0;
        
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] == nums2[j]) {
                if (result.size() == 0) result.push_back(nums1[i]);
                else if (*(result.rbegin()) != nums1[i]) result.push_back(nums1[i]);
                i++;
                j++;
            }
            else if (nums1[i] < nums2[j]) i++;
            else j++;
        }
        
        return result;
    }
};

Extensions

I think some reasonable extensions are: what if the vector-of-ints is sort of a set datatype with certain invariants (e.g., that the contents are always sorted). This suggests the results should also be sorted, but we sort of get that “for free” with the natural approach. I like discussing possible trade-offs of performance depending on the input size.

This is, in my opinion, a nice exercise on loops and arrays. More can be found here.

Arrays, Interview Questions

Find the halfway point (Code Wars 9)

This one, actually called “Equal sides of an array” threw me for a loop because I hadn’t realized we were excluding the i-th element for each possible index where we would try splitting the array. That induces some off-by-one-ish errors, which is the main interesting part.

This is a nice first approach, and it gets the goal:

def find_even_index(arr):
    if len(arr) == 0: return True
    for i in range(len(arr)):
        if sum(arr[:i]) == sum(arr[i+1:]):
            return i
    return -1

The slices-and-sums can be helper functions.

The natural sequel is to not repeat the addition so many times (so, what’s the runtime complexity of the first solution?). That requires some careful thinking and avoiding off-by-one errors.

def find_even_index(arr):
    if len(arr) == 0: return True
    leftSum = 0
    rightSum = sum(arr[1:])
    if leftSum == rightSum:
        return 0
    for i in range(1, len(arr)):
        leftSum += arr[i-1]
        rightSum -= arr[i]
        if leftSum == rightSum:
            return i
    return -1

Take-Aways

This problem seems to hit a lot of right notes: It’s approachable, it has trickiness that requires careful debugging thought, it has plausible applicability (partitioning resources evenly), and keeps the door open to optimizations. Nice! For this and other array questions, I collect them here.

Arrays, Interview Questions, Sorting

Move Zeros (Leetcode 3)

1 Comment

This problem is a fun exercise on arrays. Given an array, move all the zeros to the end of the array. Maintain the relative order of all other elements.

I have some familiarity with the C++ standard library, which includes algorithms similar-to-this (but without the relative order). In languages with very explicit memory-management, this is removing elements from the array “in spirit”. In C++, in fact, this is the solution:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        auto new_end = std::remove(std::begin(nums), std::end(nums), 0);
        std::fill(new_end, std::end(nums), 0);
    }
};

Really line 4 is the answer this problem is looking for. Really what happen is that remove “slides the contents down” to fill up the zeros. The new_end variable stores the end of the newly-shrunken array. However, the length of the original nums is unchanged — it’s up to the programmer (me) to really explicitly request that memory be freed, or otherwise messed with.

This also echoes, in a way even more directly, partitioning algorithms. We want to reorder the contents of nums such that one category of elements (those not equal to 0) are on one side, and the other category is at the other side. Again, C++ has this algorithm directly:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        std::stable_partition(std::begin(nums), std::end(nums), [](int n) { return n != 0;});
    }
};

A common critique of code (which I agree with!) is “don’t get too clever with one-liners”. I’ll stress that the above solution, in my mind, is fine because it really is just using the fact that the algorithm is exactly what the problem is asking for. Akin to using the built-in sort method for a question that asks you to sort items. C++ is just a bit verbose.

Say, however, that we don’t have such a partition algorithm. Or that the problem is explicitly asking us to implement a partition algorithm. One trick we can do here is exploit that we know how to create new 0s. In contrast to when our array might container pointers or similar, we can just “remember how many zeros to add in later”. Here’s a Python version, basically of the first C++ solution:

class Solution(object):
    def moveZeroes(self, nums):
        nextWrite = 0
        for nextRead in range(len(nums)):
            x = nums[nextRead]
            if x == 0:
                continue
            nums[nextWrite] = x
            nextWrite += 1
        for zeroOut in range(nextWrite, len(nums)):
            nums[zeroOut] = 0

Basically nextWrite serves as new_end, the first for loop is remove, and the second for loop is fill.

Say, however, instead of an array of 0s, we have an array of objects, and we’ve been partitioning them based on whether their, I don’t know, books-checked-out-of-the-library-count was 0. We couldn’t really do the above approach because we couldn’t reconstruct a whole object after-the-fact. A nice sequel problem to consider, basically, how do we “really” implement partition.

PS: This problem can be found in codewars, too. I’d say related questions are collected under array questions, or sorting questions.

Tools and Takeaways

  1. Moving elements within an array is a common sort of “vocabulary” pattern. Remove, partition, etc., are often building blocks of larger algorithms.
  2. Sometimes we may break a for-loop up into multiple “ranges”. In our first approach, we go through the “tail” of the input array to zero-out those contents.
  3. Sometimes we can recreate the same values we care about, but later. We can do this when the values are integers. Sometimes we can’t get away with that, and have to do something more sophisticated.