DyingLizard
BAN USERWhat do you mean by ZigZag iterator? Please clarify with some examples.
- DyingLizard January 06, 2018I don't think we can do better then O(N^2).
First sort the array, and iterate c from len(arr)-1 to 2. Look for a and b with starting idx as 0, and b-1.
Python Solution for the first part:
def largeArrayDiff(nums):
dic, max_dis = dict(), -1
for idx, num in enumerate(nums):
if num-1 in dic:
max_dis = max(max_dis,idx-dic[num-1])
if num not in dic:
dic[num]=idx
print('Max distance {}'.format(max_dis))
return max_dis
def main():
#largeArrayDiff
nums = [1,3,5,7,14,12,15,2,3]
#largeArrayDiff(nums)
Python solution:
def islandParameter(matrix):
def dfs(matrix, i, j):
if i<0 or j<0 or i>=len(matrix) or j>=len(matrix[0]) or not matrix[i][j]:
return 1
if matrix[i][j]==-1:
return 0
matrix[i][j], ret = -1,0
corrd = [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]
for corr in corrd:
ret += dfs(matrix, corr[0], corr[1])
return ret
res = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]:
res += dfs(matrix,i,j)
print('Islanda parameter : {}'.format(res))
def main():
#islandParameter
matrix = [[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
#islandParameter(matrix)
Python solution:
def phoneNumber(digits):
dic= {'1':'abc','2':'def','3':'ghi','4':'jkl'}
def helper(digits, curr_string, dic, res):
if not digits:
res.append(curr_string)
return
for char in dic[digits[0]]:
helper(digits[1:], curr_string+char, dic, res)
res = []
helper(str(digits), '', dic, res)
print(' possible combination of phone {}'.format(res))
return
def main():
# PhoneNumber
number = "12"
#phoneNumber(number)
Easy Python solution using tries:
def trieSearch(words, pattern):
class Trie:
def __init__(self):
self.isWord = False
self.childrens = dict()
def printTrie(trie, curr_word):
if not trie:
return
if trie.isWord:
print(curr_word)
for children, trieNode in trie.childrens.iteritems():
printTrie(trieNode,curr_word+children)
# Search funtionality for a give true and pattern
def search(trie, pattern, curr_word, res):
if not trie:
return
if (not pattern or set(pattern)=='*') and trie.isWord:
res.append(curr_word)
return
if pattern[0] in trie.childrens:
search(trie.childrens[pattern[0]], pattern[1:], curr_word + pattern[0],res)
elif pattern[0]=='*':
for char, children in trie.childrens.iteritems():
search(children, pattern, curr_word + char, res)
search(children, pattern[1:], curr_word + char, res)
root = Trie()
# Add all words in the word list to this Trie
for word in words:
temp = root
for char in word:
if char not in temp.childrens:
temp.childrens[char] = Trie()
temp = temp.childrens[char]
temp.isWord=True
# PrintTrie
printTrie(root,'')
# Search for the pattern
res = []
search(root, pattern, '', res)
print(' Result : {}'.format(res))
return res
def main():
# TrieSearch with '*'
words, pattern = ['car','cauw','cow','basdas'], 'c*w'
trieSearch(words, pattern)
Simple and Straightforward python solution using DFS search
def removeCycle(graph):
def dfs(graph, visited, vertex):
if visited[vertex]==2:
return
visited[vertex]=1
for neigbhours in graph[vertex]:
if visited[neigbhours]==1:
print('Deleting edge from {} to {}'.format(vertex,neigbhours))
graph[vertex] = list(set(graph[vertex])-set([neigbhours]))
elif visited[neigbhours]==0:
dfs(graph, visited, neigbhours)
else:
print('Graph already processed through this vertex')
visited[vertex]=2
# Visited 0 -> Not visited yet, 1-> Under process, 2-> DFS completed
visited = [0 for _ in range(len(graph)+1)]
for vertex in graph.keys():
if visited[vertex]==0:
dfs(graph, visited, vertex)
# Check if the cycles has been removed or not
print(' New Graph(without cycles)')
for key, items in graph.iteritems():
print(key,items)
return
def main():
# removeCycle in a DirectedGraph
graph = dict()
graph[1]=[2]
graph[2]=[4]
graph[3]=[2]
graph[4]=[3]
graph[5]=[2,7]
graph[6]=[5]
graph[7]=[6]
Python version : O(len(string)) complexity
def evaluateExpression(str):
stack, curr_num = [], 0
for char in str:
if char=='(':
if curr_num!=0:
stack.append(curr_num)
curr_num =0
elif char in '*-+':
stack.append(char)
curr_num = 0
elif char in '0123456789':
curr_num = curr_num*10 + int(char)
elif char == ' ':
if curr_num:
stack.append(curr_num)
curr_num = 0
elif char ==')':
if curr_num!=0:
stack.append(curr_num)
curr_num =0
num_list, res = [], 1
while stack and not isinstance(stack[-1],basestring):
num_list.append(stack.pop())
sym = stack.pop()
if sym=='+':
stack.append(sum(num_list))
elif sym=='-':
stack.append(-sum(num_list))
elif sym=='*':
for num in num_list:
res *= num
stack.append(res)
else:
print('Invalid operation!')
else:
print('Error : Invalid symbol !')
if len(stack)!=1:
print('Error ')
return stack[0]
def longestSubstringRepeating(string,k):
if not string or k==0:
return 0
max_len, start = 0, 0
dic= dict()
for idx, char in enumerate(string):
dic[char] = dic.get(char,0) + 1
while dic[char]>k:
dic[string[start]] = dic[string[start]]-1
start = start+1
max_len = max(max_len, idx-start+1)
return max_len
Python solution :
Time complexity : O(n)
def smallestSubarray(nums, target):
curr_sum, start, min_len = 0,0, sys.maxint
for idx, num in enumerate(nums):
if curr_sum + num >=target:
curr_sum += num
while curr_sum >=target and start<=idx:
min_len = min(min_len, idx-start+1)
curr_sum, start = curr_sum-nums[start], start+1
else:
curr_sum += num
return min_len if min_len!=sys.maxint else -1
def main():
# smallesSubarray sum
nums,target = [1,2,3,4,5,6,7,8,9],45
print('Smallest subarray {} '.format(smallestSubarray(nums,target)))
How will you make sure that this logic will always work.
I mean, is there any mathematic model or anything to proof that this is an impeccable model.
Algorithm : Iterate over the rows in O(num_row^2) and go through only the col indexes which differs by row indexes. If all are zero, increment the result.
- DyingLizard January 20, 2018