LeetCode – Page 5

Solution to Find Minimum in Rotated Sorted Array II by LeetCode

21 Dec

Question: https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ Question Name: Find Minimum in Rotated Sorted Array II This question is essentially the same as the prevous one.

class Solution:

# @param num, a list of integer

# @return an integer

def findMin(self, num):

if num[0] < num[-1]:

# Completely sorted

return num[0]

elif len(num) < 5:

# The input is small enough to do a linear search.

return min(num)

else:

# The length of input is greater than 2. So the division won't get

# an empty list.

# The input may be or may be not sorted.

mid = (len(num) - 1) // 2

return min(self.findMin(num[:mid]), self.findMin(num[mid:]))

Solution to Find Minimum in Rotated Sorted Array by LeetCode

20 Oct

Question: https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array/ Question Name: Find Minimum in Rotated Sorted Array

class Solution:

# @param num, a list of integer

# @return an integer

def findMin(self, num):

if num[0] < num[-1]:

# Completely sorted

return num[0]

elif len(num) < 3:

# The input is small enough to do a linear search.

return min(num)

else:

# The length of input is greater than 2. So the division won't get

# an empty list.

mid = (len(num) - 1) // 2

return min(self.findMin(num[:mid]), self.findMin(num[mid:]))

Solution to Maximum Product Subarray by LeetCode

29 Sep

Question: https://oj.leetcode.com/problems/maximum-product-subarray/ Question Name: Maximum Product Subarray The following solution is not the optimal. Because the recursion is not necessary. But recursion does make the coding easier.

class Solution:

# @param A, a list of non-zero integers

# @return an integer

def maxProductWithoutZero(self, A):

# Two base cases for this recursive method.

if len(A) == 0: return 0

if len(A) == 1: return A[0]

negativeCount = len([i for i in A if i < 0])

if negativeCount % 2 == 0:

# There are even number of negative integers. The product of all them

# is a positive integer as the maximum product among all subarrays.

return reduce(lambda x, y: x * y, A, 1)

else:

# There are odd number of negative integers. We divide the array into

# two subarray: one without the first negative integer, and the other

# without the last negative integer.

firstNeg = 0

while firstNeg < len(A):

if A[firstNeg] < 0: break

firstNeg += 1

lastNeg = len(A) - 1

while lastNeg >= 0:

if A[lastNeg] < 0: break

lastNeg -= 1

return max(self.maxProductWithoutZero(A[:lastNeg]),

self.maxProductWithoutZero(A[firstNeg + 1:]))

# @param A, a list of integers

# @return an integer

def maxProduct(self, A):

begin, end = 0, 0

if A.count(0) != 0: maxProd = 0

else: maxProd = A[0]

# Use 0 (zero) as delimiter to split the original array into small ones,

# which do not contain 0.

while end < len(A):

if A[end] != 0:

end += 1

else:

maxProd = max(maxProd, self.maxProductWithoutZero(A[begin : end]))

end += 1

begin = end

return max(maxProd, self.maxProductWithoutZero(A[begin : end]))

Solution to Reverse Words in a String by LeetCode

27 Jul

Question: https://oj.leetcode.com/problems/reverse-words-in-a-string/ Question Name: Reverse Words in a String To solve it with Python, it is as simple as one statement.

class Solution:

# @param s, a string

# @return a string

def reverseWords(self, s, method = "Stack"):

methodDic = { "Pythonic" : self.reverseWordsPythonic,

"Recursive" : self.reverseWordsRec,

"Stack" : self.reverseWordsStack,

}

methodFun = methodDic.get(method, None)

if methodFun == None: raise Exception("Require unknown method: " + method)

else: return methodFun(s)

# @param s, a string

# @return a string

def reverseWordsStack(self, s):

''' Solve it with a stack

'''

stack = []

index = 0

while index < len(s):

nextWord = ""

# Skip the spaces

while index < len(s) and s[index] == " ": index += 1

# Extract the next non-space word

while index < len(s) and s[index] != " ":

nextWord += s[index]

index += 1

# Push the word into stack. So that when we pop them out later,

# the order is reversed.

if nextWord != "": stack.append(nextWord)

if len(stack) == 0: # No word is in the s

return ""

else:

result = stack.pop()

while len(stack) != 0: result += " " + stack.pop()

return result

# @param s, a string

# @return a string

def reverseWordsRec(self, s):

''' Solve it in a recursive method

'''

# Reach the end.

if s == "": return ""

firstWord = "" # Find the first word in the remaining content.

index = 0

# Skip the heading spaces.

while index < len(s) and s[index] == " ": index += 1

# Extract the first non-space word.

while index < len(s) and s[index] != " ":

firstWord += s[index]

index += 1

# Recursively get the result for the remaining part.

remaining = self.reverseWordsRec(s[index:])

# This is the last word or the tailing spaces.

if remaining == "": return firstWord

# THis word is not in the last position.

else: return remaining + " " + firstWord

# @param s, a string

# @return a string

def reverseWordsPythonic(self, s):

''' Solve it in a Pythonic way.

'''

return " ".join(s.split()[::-1])

But is there a better way? Anyone, who read the excellent book Programming Pearls before, might remember Doug McIlroy’s … Read More »

Solution to Evaluate Reverse Polish Notation by LeetCode

27 Jul

Question: https://oj.leetcode.com/problems/evaluate-reverse-polish-notation/ Question Name: Evaluate Reverse Polish Notation

class Solution:

# @param tokens, a list of string

# @return an integer

def evalRPN(self, tokens, method = "Ite"):

if method == "Ite":

return self.evalRPNIte(tokens)

elif method == "Rec":

return self.evalRPNRec(tokens)

else:

raise Exception("Invalid method.")

# @param tokens, a list of string

# @return an integer

def evalRPNIte(self, tokens):

''' Eval the RPN in an iterative method.

'''

waiting = []

while len(tokens) != 0:

token = tokens.pop()

if not token in set(["+", "-", "*", "/"]):

# This is an operand.

token = int(token)

while len(waiting) != 0 and type(waiting[-1]) == int:

otherOperand = waiting.pop()

operator = waiting.pop()

if operator == "+":

token += otherOperand

elif operator == "-":

token -= otherOperand

elif operator == "*":

token *= otherOperand

elif operator == "/":

# http://stackoverflow.com/questions/5535206/python-negative-integer-division-surprising-result

# Because Python uses floor division. (-6) / 7 = -1, and -(6 / 7) = 0.

if (token > 0 and otherOperand > 0) or

(token < 0 and otherOperand < 0):

token = abs(token) // abs(otherOperand)

else:

token = - (abs(token) // abs(otherOperand))

else:

raise Exception("Unknown Token.")

waiting.append(token)

else:

# This is an operator.

waiting.append(token)

return waiting[-1]

# @param tokens, a list of string

# @return an integer

def evalRPNRec(self, tokens):

''' Eval the RPN in a recursive method.

'''

assert len(tokens) != 0

token = tokens.pop()

if not token in set(["+", "-", "*", "/"]):

# This is an operand.

return int(token)

else:

# This is an operator.

# The corresponding operands are in the stack. So the second

# operand is on the top of the first one.

secondParameter = self.evalRPN(tokens)

firstParameter = self.evalRPN(tokens)

if token == "+":

return firstParameter + secondParameter

elif token == "-":

return firstParameter - secondParameter

elif token == "*":

return firstParameter * secondParameter

elif token == "/":

# http://stackoverflow.com/questions/5535206/python-negative-integer-division-surprising-result

# Because Python uses floor division. (-6) / 7 = -1, and -(6 / 7) = 0.

if secondParameter == 0:

raise ZeroDivisionError()

elif firstParameter > 0 and secondParameter > 0:

return firstParameter // secondParameter

elif firstParameter < 0 and secondParameter > 0:

return - ((-firstParameter) // secondParameter)

elif firstParameter > 0 and secondParameter < 0:

return - (firstParameter // (-secondParameter))

else:

return (-firstParameter) // (-secondParameter)

else:

raise Exception("Unknown Token.")

Solution to Max Points on a Line by LeetCode

27 Jul

Question: https://oj.leetcode.com/problems/max-points-on-a-line/ Question Name: Max Points on a Line

# Definition for a point

# class Point:

# def __init__(self, a=0, b=0):

# self.x = a

# self.y = b

class Solution:

# @param a, an integer

# @param b, an integer

# @return an integer, the Greatest Common Divisor of a and b.

def _getGCD(self, a, b):

''' Compute the Greatest Common Divisor of a and b.

'''

if a < b: a, b = b, a

if a % b != 0: return self._getGCD(b, a%b)

else: return b

# @param points, a list of Points

# @return an integer

def maxPoints(self, points):

if len(points) == 0: return 0

maxCount = 1 # For a single point

for index in xrange(len(points)-1):

point = points[index]

maxCountForThisPoint = 0

# Each to-compare point must fall into one of the following

# four cases.

vertical = 0 # The two points are on one vertical line.

horizontal = 0 # The two points are on one horizontal line.

samePos = 1 # The points are in one completely same position.

# At least it has the same position as itself.

slop = {} # For all the other cases.

for toCmp in points[index+1:]:

diffX = toCmp.x - point.x

diffY = toCmp.y - point.y

if diffX == 0 and diffY == 0:

samePos += 1

elif diffX == 0:

vertical += 1

elif diffY == 0:

horizontal += 1

else:

# Make sure either:

# Both diffX and diffY are positive;

# OR

# diffX is negative while diffY positive.

# So that we can get slop(-5,3) == slop(5,-3).

if diffX < 0 and diffY < 0:

diffX, diffY = -diffX, -diffY

elif diffX < 0 or diffY < 0:

diffX, diffY = -abs(diffX), abs(diffY)

# Simplify the diffX and diffY. So that we could

# get slop(5, 10) == slop(1,2).

gcd = self._getGCD(abs(diffX), diffY)

diffX //= gcd

diffY //= gcd

slop[(diffX, diffY)] = slop.get((diffX, diffY), 0) + 1

# Find the maximum number of points that lie on the same straight line,

# which cross the current point.

if len(slop) != 0: maxCountForThisPoint = max(slop.values())

maxCountForThisPoint = max(vertical, horizontal, maxCountForThisPoint)

maxCountForThisPoint += samePos

maxCount = max(maxCount, maxCountForThisPoint)

return maxCount

Solution to Sort List by LeetCode

26 Jul

Question: https://oj.leetcode.com/problems/sort-list/ Question Name: Sort List

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param head, a ListNode

# @return a ListNode

def sortList(self, head):

''' In the common sorting algorithms, there are only two, which can guarantee

Nlog(N) in the worst case. The two are merge sorting and heap sorting.

Heap sorting is apparently not suitable for this challenge, because it

requires array to store the elements.

We are going to solve this challenge with bottom-up merge sorting.

'''

if head == None: return None

mergeSize = 1 # Bottom-up merge sorting.

finishSort = False

# Add a pseudo head node to make the process uniform.

# In the original list, during the merging, the head node might change.

# But after adding this pseudo head node, the head node never changes.

pseudoHead = ListNode(-1)

pseudoHead.next = head

while not finishSort:

# Start a new round of merging.

endOfSorted = pseudoHead

while endOfSorted.next != None:

# The start position of the first merged list.

firstToSort = endOfSorted.next

# The start position of the second merged list.

secondToSort = firstToSort

for _ in xrange(mergeSize):

secondToSort = secondToSort.next

if secondToSort == None: break

if secondToSort == None:

# Reach the end of the whole list. No need to

# merge anymore.

if firstToSort == pseudoHead.next:

# Did not merge anything in this round, because

# mergeSize >= listSize. Whole list is sorted.

finishSort = True

break

# Record how many nodes in first and second list are

# merged. firstListCount will finally be mergeSize.

# secondListCount might be either less than or equal

# to mergeSize.

firstListCount, secondListCount = 0, 0

# Merge the firstToSort and secondToSort.

# Actually we do NOT need to get the end positions of

# lists. We can determine their end during the merge

# process with two counters.

# In my first answer, I found the end positions of

# both to-merge lists. It leads to Time Limit Exceeded.

while firstListCount < mergeSize and

secondListCount < mergeSize and

secondToSort != None:

if firstToSort.val <= secondToSort.val:

endOfSorted.next = firstToSort

endOfSorted = endOfSorted.next

firstToSort = firstToSort.next

firstListCount += 1

else:

endOfSorted.next = secondToSort

endOfSorted = endOfSorted.next

secondToSort = secondToSort.next

secondListCount += 1

if firstListCount == mergeSize:

# THere may be some left nodes in second to-sort list.

while secondListCount < mergeSize and

secondToSort != None:

endOfSorted.next = secondToSort

endOfSorted = endOfSorted.next

secondToSort = secondToSort.next

secondListCount += 1

else:

# THere may be some left nodes in first to-sort list.

while firstListCount < mergeSize:

endOfSorted.next = firstToSort

endOfSorted = endOfSorted.next

firstToSort = firstToSort.next

firstListCount += 1

endOfSorted.next = secondToSort

# Double the mergeSize for the next round.

mergeSize = mergeSize << 1

# Skip the pseudo head node.

return pseudoHead.next

Solution to Insertion Sort List by LeetCode

24 Jul

Question: https://oj.leetcode.com/problems/insertion-sort-list/ Question Name: Insertion Sort List

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# @param head, a ListNode

# @return a ListNode

def insertionSortList(self, head):

if head == None: return None

# Cut the list into two part: sorted and to-sort.

pseudoHead = ListNode(-1) # Sorted list

pseudoHead.next = head

current = head.next # To-sort list

head.next = None # Cut the two lists

sortedEnd = head # Optimization for sorted input

while current != None:

# Store the current's next for later use.

nextCurrent = current.next

if sortedEnd.val <= current.val:

# Append the current node at the end.

sortedEnd.next = current

current.next = None

# The node at the end of sorted list is changed.

sortedEnd = current

else:

# Insert to some place in the middle of sorted list

headOfSorted = pseudoHead

# Find the insert position. If space permitted, we could use

# a binary tree to record the sorted node. So that we could

# find the insert position with O(logN) instead of O(N).

# Because this current node will not be added at the end, we

# do not need to check the bound.

while headOfSorted.next.val < current.val:

headOfSorted = headOfSorted.next

# Insert the node

current.next = headOfSorted.next

headOfSorted.next = current

current = nextCurrent

return pseudoHead.next

Solution to LRU Cache by LeetCode

24 Jul

Question: https://oj.leetcode.com/problems/lru-cache/ Question Name: LRU Cache

100

101

102

103

104

105

106

107

108

109

110

class LRUCache:

# The following support functions for priority queue is unnecessary, if we can

# import and use Python build-in lib heapq.

# @param pos, an integer

# @return None

def _swinm(self, pos):

''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf

Support function for priority queue

'''

while pos > 0 and self.heap[(pos-1)//2][2] > self.heap[pos][2]:

# Update the position dict.

self.position[self.heap[(pos-1)//2][0]] = pos

self.position[self.heap[pos][0]] = (pos-1)//2

# Swap these two records in heap

self.heap[(pos-1)//2], self.heap[pos] =

self.heap[pos], self.heap[(pos-1)//2]

pos = (pos-1)//2

return

# @param pos, an integer

# @return None

def _sink(self, pos):

''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf

Support function for priority queue

'''

while 2*pos + 1 < self.count:

earlierSon = 2*pos + 1

# Check the time of its right son, if it exists.

if earlierSon+1 < self.count and

self.heap[earlierSon][2] > self.heap[earlierSon+1][2]:

earlierSon += 1

# Has earlier timestamp than son(s). Finish sinking.

if self.heap[earlierSon][2] > self.heap[pos][2]: break

# Swap the records in heap and position dict.

self.position[self.heap[pos][0]] = earlierSon

self.position[self.heap[earlierSon][0]] = pos

self.heap[pos], self.heap[earlierSon] = self.heap[earlierSon], self.heap[pos]

pos = earlierSon

return

# @return an array for the least recent used record, in form of [key, value, time]

def _popLRU(self):

''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf

Support function for priority queue

'''

# Nothing to pop.

if self.count == 0: return None

# Keep the to-pop record, and delete it from position dict.

result = self.heap[0]

del self.position[result[0]]

# Delete the record in the heap.

if self.count > 1:

self.heap[0] = self.heap[self.count-1]

self.count -= 1

self.position[self.heap[0][0]] = 0

self._sink(0)

else:

self.count -= 1

return result

# @param key, an integer

# @param value, an integer

# @param time, an integer

# @return None

def _addNew(self, key, value, time):

''' https://d396qusza40orc.cloudfront.net/algs4partI/slides/24PriorityQueues.pdf

Support function for priority queue

'''

if self.count == self.capacity:

# Heap is full. Make some space.

self._popLRU()

self.heap[self.count] = [key, value, time]

self.position[key] = self.count

self.count += 1

self._swinm(self.count - 1)

return

# @param capacity, an integer

def __init__(self, capacity):

# Use min heap to do find and remove the least recent used record.

self.heap = [None] * capacity # Each element: [key, value, time]

self.count = 0

self.capacity = capacity

# Used to store the mapping between key and the corresponding record's

# position in self.heap.

self.position = {}

# Record the current time

self.time = 0

# @param key, an integer

# @return an integer

def get(self, key):

self.time += 1

if key not in self.position:

# Not found in our db.

return -1

else:

# Update the used time for the record

posInHeap = self.position[key]

self.heap[posInHeap][2] = self.time

self._sink(posInHeap)

return self.heap[self.position[key]][1]

# @param key, an integer

# @param value, an integer

# @return nothing

def set(self, key, value):

self.time += 1

if key not in self.position:

# Add a new record.

self._addNew(key, value, self.time)

else:

# Update the used time and value of the existing record.

self.heap[self.position[key]][2] = self.time

self.heap[self.position[key]][1] = value

self._sink(self.position[key])

Solution to Binary Tree Postorder Traversal by LeetCode

23 Jul

Question: https://oj.leetcode.com/problems/binary-tree-postorder-traversal/ Question Name: Binary Tree Postorder Traversal

# Definition for a binary tree node

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Solution:

# @param root, a tree node

# @return a list of integers

def postorderTraversal(self, root):

# Handle with the special cast (empty input)

if root == None: return []

# Every node will be accessed twice in the stacks.

# As post order traversal required:

# The first time, we will pop and check its son(s).

# The second time, we will check its value.

# So we are using two stacks here. One for the nodes to be accessed

# for the first time. The other is used for the nodes, waiting for

# the second access.

stackPrepare = [root]

stackReady = []

result = []

while len(stackPrepare) != 0 :

current = stackPrepare.pop()

# Current node is finally read after reading its son(s). So

# it is pushed firstly.

stackReady.append(current)

# The sons are going to travel tow stacks, which are FILO.

# We want to read left son first, if it exists.

# So we push the left son first. Please notice that, in the

# first stack, it would be left -> right

# When in the second stack, it would be root -> right -> left

# And final when reading the value into result, the order is:

# left -> right -> root, as post order traversal.

if current.left != None: stackPrepare.append(current.left)

if current.right != None: stackPrepare.append(current.right)

while len(stackReady) != 0:

result.append(stackReady.pop().val)

return result

tl;dr: Please put your code into a <pre>YOUR CODE</pre> section.

Hello everyone!

If you want to ask a question about the solution. DO READ the post and comments firstly.

If you had some troubles in debugging your solution, please try to ask for help on StackOverflow, instead of here.

If you want to post some comments with code or symbol, here is the guidline.

1. To post your code, please add the code inside a <pre> </pre> section (preferred), or <code> </code>. And inside the pre or code section, you do not need to escape < > and &, e.g. no need to use < instead of <.

2. To use special symbols < and > outside the pre block, please use "<" and ">" instead.

3. If you have a comment with lots of < and >, you could add the major part of your comment into a <pre class="decode:true crayon-inline "> YOUR COMMENTS </pre> section.

Finally, if you are posting the first comment here, it usually needs moderation. Please be patient and stay tuned. Thanks!

CodeSays.com Admin

Ovi February 12, 2024 at 11:14 pm on Solution to Min-Perimeter-Rectangle by codilityExactly my question too. I tried something very similar to Sheng's solution, importing the math module and using sqrt(). Codility marked it only as 80%,...
Doron Ben Ari February 11, 2024 at 4:10 am on Solution to Min-Avg-Two-Slice by codilityInspired by Sheng's great solution, I wrote the following proof: Assume you found the slice with minimal average. Assume the first two consecutive elements of...
Ovi February 4, 2024 at 9:03 am on Solution to sigma2012 (Stone-Wall) by codility def solution(H): heights = H # geometric logic: the blocks need to be cuboid, all sides are rectagular. Nothing fancy, means that the angles...
Ovidiu Oprea February 2, 2024 at 11:06 am on Solution to Fish by codilityIt's the reason why it took me 2 weeks to finish this task (in the context of adult life with non-dev job). I was trying...
Ovi January 15, 2024 at 2:40 pm on Solution to Brackets by codilityThanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build...
parikshit verma July 5, 2023 at 8:26 am on Solution to Missing-Integer by codility def missingnum(a): st=min(a) en=max(a) b=set(range(1,en+2)) if (en<1 or st>1) : return 1 else: return min(b-set(a))
Pavankumar Nandeshwar June 26, 2023 at 8:07 am on Solution to Dwarfs-Rafting by codilityOk fixed it. gives 100%: int solution(int N, string &S, string &T) { int q = N / 2 * N / 2; int lf...
Pavankumar Nandeshwar June 26, 2023 at 5:23 am on Solution to Dwarfs-Rafting by codilityCan someone explain what is wrong with my solution in C++ ? int solution(int N, string &S, string &T) { int q = N /...
Pavankumar Nandeshwar June 23, 2023 at 10:25 pm on Solution to Flood-Depth by codilityMy C++ Solution. O(N) #include <climits> int solution(vector<int> &A) { int max_depth {}; int max_lvl = {}; int min_lvl = INT_MAX; for (unsigned int i...