LeetCode 1494, 980, 805 and 1659.
When solving coding questions, we often compress discrete binary states into an integer, which is also known as a bitmask. Such problems usually have a small input size (e.g. n ≤ 20), so enumerating every possible combination of the binary states would not result in a TLE.
Here I’ll show you four problems I found from LeetCode.
LC 980 Unique Paths III
We are given an m x n integer grid. Each square of the grid can be (1) an empty square we can walk over, represented by 0, or (2) the unique starting square represented by 1, or (3) the unique ending square represented by 2, or (4) an obstacle we cannot walk over, represented by -1. Return the number of 4-directional walks that start at the starting square, end at the ending square, and traverse all the empty squares exactly once.
This problem is essentially counting the Hamiltonian paths. We could do a DFS (depth-first search) over an augmented state space, where a state is determined by both a bitmask that represents all the squares we’ve visited and the index of the last square we reached. The destination state is the one that has all the bits set for all the empty squares and whose last square is the ending square. We just need to count how many times we encounter the destination state during the DFS.
Try this as an exercise: LC 943 Find the Shortest Superstring.
LC 1494 Parallel Courses II
We need to take n courses labeled from 1 to n (n≤15), and each semester we can take at most k courses. We are also given an array relations that represents the prerequisite relationships between the courses such that relations[i][0] must be taken before relations[i][1]. How many semesters do we need at least to complete all the courses?
At the end of a semester, we can encode our course-taking status into a bitmask such that the (i+1)th least significant bit indicates whether course i+1 has been taken. The problem is essentially finding the shortest distance from the all-zero state to the all-one state given the state transition constraints imposed by the course taking rules, and thus can be solved by a BFS (breadth-first search).
A naive implementation could take O(4^n) time, because we have 2^n states and at each state we need to enumerate O(2^n) combinations of courses for the next semester. However, at each iteration, we reach a distinct state and thus will enumerate subsets of a distinct combination of untaken courses. So the total time complexity can be reduced to O(3^n) by using a technique to enumerate all the submasks of all possible bitmasks.
A similar question: LC 698 Partition to K Equal Sum Subsets.
LC 805 Split Array With Same Average
Given an array of n integers (n≤30), return whether it’s possible to partition it into two disjoint non-empty subsets whose average values are equal.
The problem is equivalent to finding a non-empty proper subset that has the same average value as the original array. By mapping each element x into n*x-S, where S is the sum of the original array, we further reduce the problem into finding a non-empty proper subset of the converted array that has a zero sum.
It’s impossible to enumerate all the 2^n subsets of the array given the maximum input size, but it’s affordable to enumerate 2^(n/2) subsets of a half of the array. That is reminiscent of LC 548 Split Array with Equal Sum and inspires us to split the array into two halves. We calculate the sums of all the subsets of each half, and then check whether there exists a zero sum on either half or two subsets from both halves that sum up to zero.
LC 1659 Maximize Grid Happiness
We are given an m x n grid (m≤5, n≤5), a number of introverts (at most 6) and another number of extroverts (at most 6). At each cell of the grid could live either an introvert or an extrovert. A cell neighbors another if it’s to the north, south, west or east of the other. An introvert starts with 120 happiness and loses 30 happiness for each populated neighbor. An extrovert starts with 40 and gains 20 happiness for each populated neighbor. Return the maximum total happiness we can get by placing (some of) the introverts and extroverts into (some cells of) the grid.
I wasn’t able to solve this in the original weekly contest, but later I learned from others’ solutions. The idea is to do a DFS with memoization and update a running total happiness during construction. Imagine we determine the occupancy of each cell one by one, and at each cell we could place an introvert, or place an extrovert, or leave it empty.
During the search, the state we are in is determined by the index of the current cell, the number of remaining introverts, the number of remaining extroverts, and the occupancy status of the last n cells (one cell per column), which form a frontier against unvisited cells. The last piece of information can be represented by two n-bit bitmasks, one for introverts, the other for extroverts. Each bit of the bitmasks represents whether an introvert/extrovert has been placed in a certain column on the frontier. For each introvert or extrovert that we put into the grid, we consider its north and west neighbors when we place itself and consider its south and east neighbors when we place those neighbors.
Thanks for reading this! Please also check out my other posts.
