MediumNo. 2100
Find Good Days to Rob the Bank — LeetCode 2100 Python Solution
- Pattern
- Prefix Sum
- Topics
- Array, Dynamic Programming, Prefix Sum
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the ith day.
Example
- Input
- security = [5,3,3,3,5,6,2], time = 2
- Output
- [2,3]
- Explanation
- On day 2, we have security[0] >= security[1] >= security[2] <= security[3] <= security[4].
Python solution
class Solution:
def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
n = len(security)
if n <= time * 2:
return []
left, right = [0] * n, [0] * n
for i in range(1, n):
if security[i] <= security[i - 1]:
left[i] = left[i - 1] + 1
for i in range(n - 2, -1, -1):
if security[i] <= security[i + 1]:
right[i] = right[i + 1] + 1
return [i for i in range(n) if time <= min(left[i], right[i])]Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 2100. Find Good Days to Rob the Bank is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0689 | Maximum Sum of 3 Non-Overlapping Subarrays | Hard |
| 0813 | Largest Sum of Averages | Medium |
| 1000 | Minimum Cost to Merge Stones | Hard |
| 1140 | Stone Game II | Medium |
| 1444 | Number of Ways of Cutting a Pizza | Hard |
| 1524 | Number of Sub-arrays With Odd Sum | Medium |
Frequently asked questions
- How hard is LeetCode 2100. Find Good Days to Rob the Bank?
LeetCode 2100. Find Good Days to Rob the Bank is rated Medium on LeetCode.
- What topics does LeetCode 2100. Find Good Days to Rob the Bank cover?
LeetCode 2100. Find Good Days to Rob the Bank is tagged Array, Dynamic Programming and Prefix Sum on LeetCode.