Number of Ways to Select Buildings

Medium

Asked by:

8 views

Topics:

ArraysStringsTwo Pointers

You are given a 0-indexed binary string s which represents the types of buildings along a street where:

s[i] = '0' denotes that the i^th building is an office and
s[i] = '1' denotes that the i^th building is a restaurant.

As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.

For example, given s = "001101", we cannot select the 1^st, 3^rd, and 5^th buildings as that would form "011" which is not allowed due to having two consecutive buildings of the same type.

Return the number of valid ways to select 3 buildings.

Example 1:

Input: s = "001101"
Output: 6
Explanation: 
The following sets of indices selected are valid:
- [0,2,4] from "001101" forms "010"
- [0,3,4] from "001101" forms "010"
- [1,2,4] from "001101" forms "010"
- [1,3,4] from "001101" forms "010"
- [2,4,5] from "001101" forms "101"
- [3,4,5] from "001101" forms "101"
No other selection is valid. Thus, there are 6 total ways.

Example 2:

Input: s = "11100"
Output: 0
Explanation: It can be shown that there are no valid selections.

Constraints:

3 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible characters in the input string, and what are the constraints on the string's length?
If no such sequence of buildings exists, what should I return?
Does the order of the buildings matter? For example, is '010' different from '010' if they appear in different locations?
Can the input string be empty or null?
Are we only considering contiguous sequences of buildings, or can the buildings be non-adjacent?

Brute Force Solution

Approach

The brute force approach for counting building selections involves checking every single possible combination of buildings. We consider each building individually and decide whether to include it or not in our selection. By exhaustively exploring all combinations, we can count the valid ones based on the given selection rules.

Here's how the algorithm would work step-by-step:

Consider the very first building. We have two choices: either we include it in our selection, or we don't.
For each of those choices, move on to the second building. Again, we have two choices: include it, or don't.
Repeat this process for every building in the sequence. At each building, we're branching out, creating new possible selections.
After making a choice for every building (include or exclude), we have a complete potential selection.
Check if the current potential selection of buildings is valid according to the specified rules, such as not having two adjacent buildings of the same type.
If the selection is valid, increase our count of valid selections.
Repeat this entire process, trying every possible combination of including and excluding buildings until we have checked them all.
The final count represents the total number of valid selections of buildings we found.

Code Implementation

def count_building_selections_brute_force(buildings):
    number_of_buildings = len(buildings)
    number_of_valid_selections = 0

    # Iterate through all possible subsets using binary representation
    for i in range(2**number_of_buildings):
        current_selection = []
        # Construct the current selection based on the bits of i
        for building_index in range(number_of_buildings):
            if (i >> building_index) & 1:
                current_selection.append(buildings[building_index])

        is_valid = True

        # Ensure we do not access an invalid index
        if len(current_selection) > 1:
            for building_index in range(len(current_selection) - 1):
                # Check for adjacent buildings of same type
                if current_selection[building_index] == current_selection[building_index + 1]:
                    is_valid = False
                    break
        
        # Increment valid selections count, if valid
        if is_valid:
            number_of_valid_selections += 1

    return number_of_valid_selections

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible subsets of the n buildings. For each building, we have two choices: either include it in the selection or exclude it. This leads to 2 * 2 * ... * 2 (n times) possible combinations. After generating each combination, we need to check its validity, which takes O(n) time in the worst case. However, the dominant factor is the generation of 2^n subsets, so the overall time complexity is O(2^n * n). Since 2^n grows faster than n, the final Big O is O(2^n).

Space Complexity

O(N) – The described brute force approach explores all possible combinations of buildings using a recursive-like process. Each level of the recursion represents a building, and the depth of the recursion can go as deep as the number of buildings, N. Each call requires storing the current selection (included/excluded) information in a stack frame. Therefore, the maximum depth of the recursion stack is proportional to N, implying a space complexity of O(N).

Optimal Solution

Approach

The key to efficiently counting building arrangements is to avoid checking every possible combination. Instead, we focus on building valid arrangements incrementally by considering each building type (office or apartment) one at a time and leveraging information about previously built sections.

Here's how the algorithm would work step-by-step:

Imagine you are walking down the street looking at each building in sequence.
For each building you see, keep track of how many sequences of length one (just that building), length two (that building following a valid previous building), and length three (that building completing a valid sequence) you can create.
For instance, if you see an office building, add to the count of single-building sequences. Also, figure out how many two-building sequences you can form using this building and previous buildings. Finally, figure out if you can use this building to complete any three-building sequences that followed the 'office-apartment-office' or 'apartment-office-apartment' arrangement rules.
The total number of three-building sequences you've built up by the end is your answer.

Code Implementation

def number_of_ways_to_select_buildings(street):
    one_building_sequences = 0
    two_building_sequences = 0
    three_building_sequences = 0

    for building in street:
        if building == '0': # Current building is an office
            three_building_sequences += two_building_sequences

            # Adding to single building sequences.
            one_building_sequences += 1

            two_building_sequences += one_building_sequences - 1
        else: # Current building is an apartment building
            three_building_sequences += two_building_sequences

            one_building_sequences += 1

            # Increment two building sequences, using the previous count
            two_building_sequences += one_building_sequences - 1

    return three_building_sequences

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each building in the input sequence once. For each building, it updates a constant number of counters representing the counts of valid sequences of length one, two, and three. The number of operations performed for each building is independent of the input size, resulting in a linear relationship between the number of buildings (n) and the total number of operations. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm maintains a constant number of variables to track the counts of sequences of length one, two, and three. Specifically, it seems to be storing counts for the number of 'office' and 'apartment' buildings encountered, the number of valid two-building sequences, and the final count of valid three-building sequences. Since the number of these variables does not depend on the input size N (the number of buildings), the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 if the input string is null or empty as there are no buildings to select.
Input string with length less than 3	Return 0 as at least three characters are needed to form a valid building sequence.
Input string with only '0's	The '1' count will be zero leading to a zero product, thus 0 valid building sequences.
Input string with only '1's	The '0' count will be zero leading to a zero product, thus 0 valid building sequences.
Large input string exceeding memory constraints	Optimize the solution to use constant space, avoiding storing large intermediate results.
Input string contains characters other than '0' and '1'	Throw an IllegalArgumentException or return an error code to indicate invalid input.
Input string with alternating '0' and '1' characters (e.g., '010101')	The counts of '0' and '1' will be approximately equal, potentially maximizing the number of valid sequences, ensure multiplication of the counts doesn't lead to integer overflow.
Input string with a skewed distribution of '0's and '1's (e.g., many '0's followed by a few '1's)	The number of possible selections will depend on the scarcity of one of the digits, so the algorithm should handle cases where one digit is rare.

Null or empty input string

How to Handle:

Return 0 if the input string is null or empty as there are no buildings to select.

Input string with length less than 3

How to Handle:

Return 0 as at least three characters are needed to form a valid building sequence.

Input string with only '0's

How to Handle:

The '1' count will be zero leading to a zero product, thus 0 valid building sequences.

Input string with only '1's

How to Handle:

The '0' count will be zero leading to a zero product, thus 0 valid building sequences.

Large input string exceeding memory constraints

How to Handle:

Optimize the solution to use constant space, avoiding storing large intermediate results.

Input string contains characters other than '0' and '1'

How to Handle:

Throw an IllegalArgumentException or return an error code to indicate invalid input.

Input string with alternating '0' and '1' characters (e.g., '010101')

How to Handle:

The counts of '0' and '1' will be approximately equal, potentially maximizing the number of valid sequences, ensure multiplication of the counts doesn't lead to integer overflow.

Input string with a skewed distribution of '0's and '1's (e.g., many '0's followed by a few '1's)

How to Handle:

The number of possible selections will depend on the scarcity of one of the digits, so the algorithm should handle cases where one digit is rare.