How do you solve Number of Ways to Select Buildings on LeetCode?

Number of Ways to Select Buildings (LeetCode #2222) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The problem can be simplified by focusing on the patterns of '01' and '10'.

What is the time complexity of Number of Ways to Select Buildings?

The optimal solution for Number of Ways to Select Buildings runs in O(n) time and uses O(n) space. This complexity is linear because we only traverse the string a couple of times, making it efficient for larger inputs.

What is the brute force solution for Number of Ways to Select Buildings?

The brute force approach for Number of Ways to Select Buildings is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking all possible combinations of three buildings to see if they meet the criteria of alternating types. This is straightforward but inefficient for larger strings. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Number of Ways to Select Buildings?

Number of Ways to Select Buildings uses the following concepts: String, Dynamic Programming, Prefix Sum. The recommended patterns to study are: Dynamic Programming, Prefix Sum.

What are the interview tips for Number of Ways to Select Buildings?

Always start with a brute-force solution to understand the problem better. Look for patterns in the data that can simplify the problem. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Number of Ways to Select Buildings?

Not considering the need for non-consecutive buildings of the same type. Overlooking the importance of counting pairs before forming triplets.

#2222

Number of Ways to Select Buildings

Medium

StringDynamic ProgrammingPrefix SumDynamic ProgrammingPrefix Sum

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach involves counting the valid '01' and '10' pairs in the string and using these counts to calculate the total combinations. This reduces the problem to linear time complexity.

⚙️

Algorithm

4 steps

1Step 1: Initialize two arrays to count the number of '01' and '10' pairs up to each index.
2Step 2: Traverse the string to fill these arrays based on the current and previous characters.
3Step 3: For each '0' found, add the count of '10' pairs that can be formed with '0' as the last building.
4Step 4: For each '1' found, add the count of '01' pairs that can be formed with '1' as the last building.

solution.py24 lines

1# Full working Python code
2
3def countWays(s):
4    n = len(s)
5    count01 = [0] * n
6    count10 = [0] * n
7    count = 0
8
9    for i in range(1, n):
10        count01[i] = count01[i - 1]
11        count10[i] = count10[i - 1]
12        if s[i - 1:i + 1] == '01':
13            count01[i] += 1
14        elif s[i - 1:i + 1] == '10':
15            count10[i] += 1
16
17    for i in range(n):
18        if s[i] == '0':
19            count += count10[i]
20        elif s[i] == '1':
21            count += count01[i]
22
23    return count
24

ℹ

Complexity note: This complexity is linear because we only traverse the string a couple of times, making it efficient for larger inputs.

1The problem can be simplified by focusing on the patterns of '01' and '10'.
2Counting valid pairs allows us to avoid the inefficiencies of checking every combination.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.