Prefix/Postfix Flashcards
- Plates Between Candles
Solved
Medium
Topics
Companies Amazon
Hint
There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters ‘’ and ‘|’ only, where a ‘’ represents a plate and a ‘|’ represents a candle.
You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti…righti] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.
For example, s = “|||||”, and a query [3, 8] denotes the substring “||**|”. The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.
Return an integer array answer where answer[i] is the answer to the ith query.
Example 1:
ex-1
Input: s = “||***|”, queries = [[2,5],[5,9]]
Output: [2,3]
Explanation:
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.
Example 2:
ex-2
Input: s = “|**||||**|*”, queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation:
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.
Constraints:
3 <= s.length <= 105
s consists of ‘*’ and ‘|’ characters.
1 <= queries.length <= 105
queries[i].length == 2
0 <= lefti <= righti < s.length
https://leetcode.com/problems/plates-between-candles/
from functools import reduce
from itertools import accumulate
class Solution:
def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
right_candle = [0] *len(s)
left_candle = [0] * len(s)
n = len(s)
candle = float('-inf')
for i, c in enumerate(s):
if c == "|":
candle = i
left_candle[i] = candle
candle = float('inf')
for i, c in reversed(list(enumerate(s))):
if c == '|':
candle = i
right_candle[i] = candle
prefix_stars = list(accumulate(map(lambda c: 0 if c == '|' else 1, s)))
out = []
for query in queries:
ql, qr = query
lb = right_candle[ql]
rb = left_candle[qr]
if lb > rb:
out.append(0)
else:
out.append(prefix_stars[rb] - prefix_stars[lb])
return out- Product of Array Except Self
Medium
Companies: Facebook, Many others
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 105
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
https://leetcode.com/problems/product-of-array-except-self/
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
n = len(nums)
output = [1] * n
for i in range(1, n):
output[i] = output[i-1] * nums[i-1]
right_bounds = 1
for i in range(n-1, -1, -1):
output[i] = output[i] * right_bounds
right_bounds = nums[i] * right_bounds
return output
- Subarray Sum Equals K
Solved
Medium
Topics
Companies
Hint
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Constraints:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
https://leetcode.com/problems/subarray-sum-equals-k/description/
from collections import defaultdict
class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
ret = 0
m = defaultdict(int)
m[0] = 1
prefix = 0
for i in range(len(nums)):
prefix += nums[i]
diff = prefix - k
if diff in m:
ret += m[diff]
m[prefix] += 1
return ret
Concise
~~~
from collections import defaultdict
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
sumstore = defaultdict(int)
sumstore[0] = 1
prefixSum = 0
ret = 0
for num in nums:
prefixSum += num
ret += sumstore[prefixSum-k]
sumstore[prefixSum] += 1
return ret
~~~
Instead of considering all the startstartstart and endendend points and then finding the sum for each subarray corresponding to those points, we can directly find the sum on the go while considering different endendend points. i.e. We can choose a particular startstartstart point and while iterating over the endendend points, we can add the element corresponding to the endendend point to the sum formed till now. Whenever the sumsumsum equals the required kkk value, we can update the countcountcount value. We do so while iterating over all the endendend indices possible for every startstartstart index. Whenever, we update the startstartstart index, we need to reset the sumsumsum value to 0.
- Maximum Swap
Medium
Companies: facebook 2024
You are given an integer num. You can swap two digits at most once to get the maximum valued number.
Return the maximum valued number you can get.
Example 1:
Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
Example 2:
Input: num = 9973
Output: 9973
Explanation: No swap.
Constraints:
0 <= num <= 108
O(n), O(n) - Follow up do in O(1) Space
https://leetcode.com/problems/maximum-swap/description/
O(n) O(n) Solution:
Get Suffix Max Sum at idx and then use it to swap elements.
class Solution(object):
def maximumSwap(self, num):
"""
:type num: int
:rtype: int
"""
digits = []
while num:
dig = num % 10
num = num//10
digits.append(dig)
digits = digits[::-1]
n = len(digits)
suffix_max = [0] * n
suffix_max[n-1] = (digits[-1], n-1)
for i in range(n-2, -1, -1):
if digits[i] > suffix_max[i+1][0]:
suffix_max[i] = (digits[i], i)
else:
suffix_max[i] = suffix_max[i+1]
for i in range(len(digits) - 1):
maxdigit, idx = suffix_max[i+1]
if digits[i] < maxdigit:
digits[i], digits[idx] = digits[idx], digits[i]
break
ret = 0
for d in digits:
ret = (ret * 10) + d
return ret
O(n), O(1) Space
Calculate max idx as you go through reverse, and if element at i is smaller than max_idx, designate it’s idx to swap in the end.
from functools import reduce
class Solution:
def maximumSwap(self, num: int) -> int:
digits = []
while num:
digits.append(num%10)
num = num // 10
digits = digits[::-1]
n = len(digits)
max_digit = len(digits) - 1
swap_i, swap_j = 0,0
for i in range(n-2, -1, -1):
if digits[i] > digits[max_digit]:
max_digit = i
elif digits[i] < digits[max_digit]:
swap_i = i
swap_j = max_digit
digits[swap_i], digits[swap_j] = digits[swap_j], digits[swap_i]
return reduce(lambda n, c: n*10 + c, digits)
- Range Sum Query - Immutable
Solved
Easy
Topics
Companies
Given an integer array nums, handle multiple queries of the following type:
Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.
Implement the NumArray class:
NumArray(int[] nums) Initializes the object with the integer array nums. int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).
Example 1:
Input
[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]
Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
Constraints:
1 <= nums.length <= 104 -105 <= nums[i] <= 105 0 <= left <= right < nums.length At most 104 calls will be made to sumRange.
https://leetcode.com/problems/range-sum-query-immutable/description/
from itertools import accumulate
class NumArray:
def \_\_init\_\_(self, nums: List[int]):
self.prefix_sum = list(accumulate(nums))
def sumRange(self, left: int, right: int) -> int:
leftPrefix = 0
if left > 0:
leftPrefix = self.prefix_sum[left-1]
return self.prefix_sum[right] - leftPrefix- Range Sum Query 2D - Immutable
Solved
Medium
Topics
Companies
Given a 2D matrix matrix, handle multiple queries of the following type:
Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Implement the NumMatrix class:
NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix. int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
You must design an algorithm where sumRegion works on O(1) time complexity.
Example 1:
Input
[“NumMatrix”, “sumRegion”, “sumRegion”, “sumRegion”]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]
Explanation
NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)
Constraints:
m == matrix.length n == matrix[i].length 1 <= m, n <= 200 -104 <= matrix[i][j] <= 104 0 <= row1 <= row2 < m 0 <= col1 <= col2 < n At most 104 calls will be made to sumRegion.
Hint: Prefix rows left - right for 1D , what else to accumulate in 2D?
https://leetcode.com/problems/range-sum-query-2d-immutable/description/
Key here is to include the top left corner that will get subtracted twice if row1 > 0 and col1 > 0
~~~
from itertools import accumulate
class NumMatrix:
def \_\_init\_\_(self, matrix: List[List[int]]):
row_prefix = list(map(lambda x: list(accumulate(x)), matrix))
self.prefix_sum = list(accumulate(row_prefix, lambda a,b: [i+j for i,j in zip(a,b)]))
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
row_exclude = 0
col_exclude = 0
col_add = 0
if row1 > 0:
row_exclude = self.prefix_sum[row1-1][col2]
if col1 > 0:
col_add = self.prefix_sum[row1-1][col1-1]
if col1 > 0:
col_exclude = self.prefix_sum[row2][col1-1]
return self.prefix_sum[row2][col2] - (row_exclude + col_exclude) + (col_add) ~~~
