leetcode-015

Alpha

Find All Anagrams in a String
Grumpy Bookstore Owner
Add Two Numbers II
Longest Consecutive Sequence
Prison Cells After N Days

String to Integer (atoi)
Contiguous Array
Minimum Size Subarray Sum
Consecutive Numbers Sum
Sliding Puzzle

Beta

EQ-1 *

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
Input: s: "cbaebabacd" p: "abc" Output: [0, 6]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# 438. Find All Anagrams in a String

class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
if ns < np:
return []

p_count, s_count = [0] * 26, [0] * 26
# build reference array using string p
for ch in p:
p_count[ord(ch) - ord('a')] += 1

output = []
# sliding window on the string s
for i in range(ns):
# add one more letter
# on the right side of the window
s_count[ord(s[i]) - ord('a')] += 1
# remove one letter
# from the left side of the window
if i >= np:
s_count[ord(s[i - np]) - ord('a')] -= 1
# compare array in the sliding window
# with the reference array
if p_count == s_count:
output.append(i - np + 1)

return output


from collections import Counter
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ns, np = len(s), len(p)
if ns < np:
return []

p_count = Counter(p)
s_count = Counter()

output = []
# sliding window on the string s
for i in range(ns):
# add one more letter
# on the right side of the window
s_count[s[i]] += 1
# remove one letter
# from the left side of the window
if i >= np:
if s_count[s[i - np]] == 1:
del s_count[s[i - np]]
else:
s_count[s[i - np]] -= 1
# compare array in the sliding window
# with the reference array
if p_count == s_count:
output.append(i - np + 1)

return output

# sliding window on the string s

# add one more letter on the right side of the window
# remove one letter from the left side of the window
# compare array in the sliding window with the reference array

EQ-2

Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.
On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.
The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.
Return the maximum number of customers that can be satisfied throughout the day.
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 Output: 16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 1052. Grumpy Bookstore Owner

class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
n = len(customers)
if not n: return 0

pre_sum1, pre_sum2 = [0], [0]
for gru, cust in zip(grumpy, customers):
if gru:
pre_sum1.append(pre_sum1[-1])
pre_sum2.append(pre_sum2[-1] + cust)
else:
pre_sum1.append(pre_sum1[-1] + cust)
pre_sum2.append(pre_sum2[-1])

max_sat, add_sat = -1, -1
for i in range(X, n+1):
# print(i, i-X, pre_sum2[i], pre_sum2[i-X])
if pre_sum2[i] - pre_sum2[i-X] > max_sat:
max_sat = pre_sum2[i] - pre_sum2[i-X]
add_sat = i

return pre_sum1[-1] + max_sat

EQ-3

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 445. Add Two Numbers II

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
total = self.get_list_sum(l1) + self.get_list_sum(l2)
dummy = ListNode(1)
prev = dummy

for c in str(total):
prev.next = ListNode(int(c))
prev = prev.next

return dummy.next


def get_list_sum(self, head):
sum = 0
current = head

while current:
sum *= 10
sum += current.val
current = current.next

return sum

EQ-4

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Input: [100, 4, 200, 1, 3, 2] Output: 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 128. Longest Consecutive Sequence

class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
longest_streak = 0
num_set = set(nums)

for num in num_set:
if num - 1 not in num_set:
current_num = num
current_streak = 1

while current_num + 1 in num_set:
current_num += 1
current_streak += 1

longest_streak = max(longest_streak, current_streak)

return longest_streak

EQ-5

There are 8 prison cells in a row, and each cell is either occupied or vacant.
Each day, whether the cell is occupied or vacant changes according to the following rules:

  • If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
  • Otherwise, it becomes vacant.
    (Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.
Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 957. Prison Cells After N Days

class Solution:
def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
N = (N-1) % 14 # It's a repeating pattern for every 14 days
for day in range(N+1): # +1 to make sure it runs for atleast 1 cycle
temp = [] # temp = [0]*8
temp.append(0)

for cell in range(1, 7):
temp.append(1 if cells[cell - 1] == cells[cell + 1] else 0)

temp.append(0)
cells = temp

return cells



class Solution1:
def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]:
seen = {str(cells): N}
while N:
seen.setdefault(str(cells), N)
N -= 1
cells = [0] + [cells[i - 1] ^ cells[i + 1] ^ 1 for i in range(1, 7)] + [0]
if str(cells) in seen:
N %= seen[str(cells)] - N
return cells

EQ-6

Implement atoi which converts a string to an integer.
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned.

Note:
Only the space character ‘ ‘ is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# 8. String to Integer (atoi)

class Solution1:
def myAtoi(self, str: str) -> int:

str = str.strip()
str = re.findall('(^[\+\-0]*\d+)\D*', str)

try:
result = int(''.join(str))
MAX_INT = 2147483647
MIN_INT = -2147483648
if result > MAX_INT > 0:
return MAX_INT
elif result < MIN_INT < 0:
return MIN_INT
else:
return result
except:
return 0


class Solution:
def myAtoi(self, str: str) -> int:
no_whitespace = str.strip()
negative = False

print('no_whitespace: ', no_whitespace)
if len(no_whitespace) == 0:
return 0

if no_whitespace[0] == '-':
no_whitespace = no_whitespace[1:]
negative = True
elif no_whitespace[0] == '+':
no_whitespace = no_whitespace[1:]

number_str = []
for i, n in enumerate(no_whitespace):
if not n.isnumeric():
break
number_str.append(n)

number = 0
if len(number_str) > 0:
number = int(''.join(number_str))
if negative:
number *= -1

INT_MIN = -2**31
INT_MAX = 2**31 - 1
if number < INT_MIN:
number = INT_MIN
elif number > INT_MAX:
number = INT_MAX

return number

EQ-7

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 525. Contiguous Array

class Solution:
def findMaxLength(self, nums: List[int]) -> int:
count = 0
max_length=0
table = {0: 0}

for index, num in enumerate(nums, 1):
if num == 0:
count -= 1
else:
count += 1

if count in table:
max_length = max(max_length, index - table[count])
else:
table[count] = index

return max_length

https://leetcode.com/problems/contiguous-array/discuss/99655/Python-O(n)-Solution-with-Visual-Explanation

EQ-8

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.
Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint.

1
2
3
4
5
6
7
8
9
10
11
12
13
# 209. Minimum Size Subarray Sum

class Solution1:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
total = left = 0
result = len(nums) + 1
for right, n in enumerate(nums):
total += n
while total >= s:
result = min(result, right - left + 1)
total -= nums[left]
left += 1
return result if result <= len(nums) else 0

EQ-9

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?
Input: 15 Output: 4 Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 829. Consecutive Numbers Sum

class Solution: # Mathematical (Fast)
def consecutiveNumbersSum(self, N: int) -> int:
res = 1
i = 3
while N % 2 == 0:
N /= 2
while i * i <= N:
count = 0
while N % i == 0:
N /= i
count += 1
res *= count + 1
i += 2
return res if N == 1 else res * 2

EQ-10 *

On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.
A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.
The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].
Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 773. Sliding Puzzle

class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
moves, used, cnt =
{0: {1, 3}, 1:{0, 2, 4}, 2:{1, 5}, 3:{0, 4}, 4:{1, 3, 5}, 5:{2, 4}}, set(), 0
s = "".join(str(c) for row in board for c in row)
q = [(s, s.index("0"))]
while q:
new = []
for s, i in q:
used.add(s)
if s == "123450":
return cnt
arr = [c for c in s]
for move in moves[i]:
new_arr = arr[:]
new_arr[i], new_arr[move] = new_arr[move], new_arr[i]
new_s = "".join(new_arr)
if new_s not in used:
new.append((new_s, move))
cnt += 1
q = new
return -1

Sigma

Feb 13, 2020
La Jolla, CA

Omega

https://leetcode.com/