LeetCode – Page 12

Solution to Remove Duplicates from Sorted List II by LeetCode

23 Jun

Question: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ Question Name: Remove Duplicates from Sorted List II

class Solution:

# @param head, a ListNode

# @return a ListNode

def deleteDuplicates(self, head):

# Handle special case that the list is empty

if head == None: return head

# Add a pseudo head node to make the process uniform

tempHead = ListNode(head.val ^ 0x1)

tempHead.next = head

current = tempHead

while current.next != None:

nextVal = current.next

if nextVal.next != None and nextVal.val == nextVal.next.val:

# This element and its next one are the same.

# They are duplicate. We are going to remove

# all the nodes with this value from the list.

nextVal = nextVal.next

while nextVal.next != None and nextVal.val == nextVal.next.val:

nextVal = nextVal.next

current.next = nextVal.next

else:

current = current.next

# Skip the pseudo head node, and return the real one.

return tempHead.next

Solution to Remove Duplicates from Sorted List by LeetCode

23 Jun

Question: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/ Question Name: Remove Duplicates from Sorted 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 deleteDuplicates(self, head):

# Handle special case that the list is empty

if head == None: return head

current = head

# Travel the list until the second last node

while current.next != None:

if current.val == current.next.val:

# This element and the next one are the same.

# They are duplicate. We are going to remove

# the next node.

temp = current.next

current.next = current.next.next

del temp

else:

current = current.next

return head

Solution to Largest Rectangle in Histogram by LeetCode

23 Jun

Question: https://oj.leetcode.com/problems/largest-rectangle-in-histogram/ Question name: Largest Rectangle in Histogram

class Solution:

class Status(object):

''' A class to store the intermediate status of the dividing zone.

A name tuple is better if it is allowed.

'''

__slots__ = ["heightIndex", "begin", "end"]

def __init__(self, heightIndex, begin, end):

self.heightIndex = heightIndex

self.begin = begin

self.end = end

return

# @param height, a list of integer

# @return an integer

def largestRectangleArea(self, height):

height = sorted(enumerate(height), key = lambda x: x[1])

# All bars have non-negative height. Area is at least 0.

maxArea = 0

# Initialize the stack. Recursive solution will lead to stack overflow

stack = [self.Status(0, 0, len(height)-1)]

while len(stack) != 0:

subSection = stack.pop()

# Terminate case

if subSection.begin > subSection.end: continue

# Skip the bars if they are not in current zone [begin, end].

while not subSection.begin <= height[subSection.heightIndex][0]

<= subSection.end:

subSection.heightIndex += 1

# Liebig's law of the minimum. The height of the rectangle

# is determined by the lowest bar.

area = (subSection.end - subSection.begin + 1) *

height[subSection.heightIndex][1]

maxArea = max(maxArea, area)

# All the bars in current zone [begin, end] have the same height.

# No lower bar, so no need to divide current zone.

if height[subSection.heightIndex][1] == height[-1][1]: continue

# Divide current zone with the lowest bar. Only after removing

# the lowest bar, the height of new zones could be higher

# (also possibly keep the same).

# Left part of current zone.

stack.append(self.Status(subSection.heightIndex+1,

subSection.begin,

height[subSection.heightIndex][0]-1))

# Right part of current zone.

stack.append(self.Status(subSection.heightIndex+1,

height[subSection.heightIndex][0]+1,

subSection.end))

return maxArea

Update on 2014-06-24: Thanks to optimization, the previous solution passed all the tests. But when I met with the question “Maximal Rectangle”, I realized the previous one is not the designed … Read More »

Solution to Remove Duplicates from Sorted Array II by LeetCode

20 Jun

Question: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/ Question Name: Remove Duplicates from Sorted Array II The second previous element might be overwritten in the last round.

class Solution:

# @param A a list of integers

# @return an integer

def removeDuplicates(self, A):

if len(A) < 3: return len(A)

front, back = 2, 2

secondPre = A[front-2]

while front < len(A):

if A[front] == A[front-1] and A[front] == secondPre:

secondPre = A[front-1]

else:

secondPre = A[front-1]

A[back] = A[front]

back += 1

front += 1

return back

Well, inspired by http://www.mitbbs.com/article_t/JobHunting/32770131.html, there is a better and more generic solution as:

class Solution:

# @param A a list of integers

# @param M the times that duplicates are allowed

# @return an integer

def _removeDuplicatesHelper(self, A, M):

''' Remove some duplicate items in A. So that one single item

appears at most M times.

'''

if len(A) < 2: return len(A)

toWrite = 1 # The position for next write. And toWrite - 1

# is th previous appeared item.

count = 1 # The occurrence of previous appeared item.

for index in xrange(1, len(A)):

if A[index] == A[toWrite-1]:

# Is a duplicate item, being the same as the previous one.

count += 1

if count <= M:

# It is allowed to appear M times or less.

A[toWrite] = A[index]

toWrite += 1

else:

# Meet with a new item.

A[toWrite] = A[index]

toWrite += 1

count = 1

return toWrite

# @param A a list of integers

# @return an integer

def removeDuplicates(self, A):

return self._removeDuplicatesHelper(A, 2)

With the parameter M … Read More »

Solution to Search in Rotated Sorted Array II by LeetCode

20 Jun

Question: https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/ Question Name: Search in Rotated Sorted Array II I did not notice, there is no duplicate in Search in Rotated Sorted Array. SO I’ve done this in that question.

class Solution:

# @param A, a list of integers

# @param target, an integer to be searched

# @return an integer

def _searchHelper(self, A, target, begin, end):

if begin > end: return -1

mid = (begin + end) // 2

if A[begin] < A[end]: rotated = False

else: rotated = True

if A[mid] == target:

return mid

elif A[mid] < target:

if rotated:

temp = self._searchHelper(A, target, begin, mid - 1)

if temp != -1: return temp

return self._searchHelper(A, target, mid + 1, end)

else:

if rotated:

temp = self._searchHelper(A, target, mid + 1, end)

if temp != -1: return temp

return self._searchHelper(A, target, begin, mid - 1)

# @param A, a list of integers

# @param target, an integer to be searched

# @return a boolean

def search(self, A, target):

if self._searchHelper(A, target, 0, len(A)-1) == -1:

return False

else:

return True

Solution to Combinations by LeetCode

20 Jun

Question: https://oj.leetcode.com/problems/combinations/ Question Name: Combinations

class Solution:

# @return a list of lists of integers

def combine(self, n, k):

pool = range(1, n+1) # The candidates to choose

limit = 1 << len(pool)

current = 0 # In current, bit[i] == 1 means S[i] is chosen.

result = []

while current < limit:

# Construct the list for "current"

temp = []

for index in xrange(len(pool)):

if (1 << index) & current != 0:

temp.append(pool[index])

if len(temp) > k: # List is too long

break

else:

if len(temp) == k: # List is qualified for result

result.append(temp)

# Else, it is too short

current += 1

return result

Solution to Subsets by LeetCode

20 Jun

Question: https://oj.leetcode.com/problems/subsets/ Question Name: Subsets

class Solution:

# @param S, a list of integer

# @return a list of lists of integer

def subsets(self, S):

''' A problem to test the bit operation.

'''

S.sort() # Make sure the result is non-descending order.

limit = 1 << len(S)

current = 0 # In current, bit[i] == 1 means S[i] is chosen.

result = []

while current < limit:

# Construct the list for "current"

temp = []

for index in xrange(len(S)):

if (1 << index) & current != 0:

temp.append(S[index])

result.append(temp)

current += 1

return result

Solution to Word Search by LeetCode

19 Jun

Question: https://oj.leetcode.com/problems/word-search/ Question Name: Word Search The description and comments are misleading. Comments says “@param board, a list of lists of 1 length string”. And in the example, the input board is [[“ABCE”], [“SFCS”], [“ADEE”]]. But actually, in the tests, … Read More »

Solution to Minimum Window Substring by LeetCode

19 Jun

Question: https://oj.leetcode.com/problems/minimum-window-substring/ Question Name: Minimum Window Substring

class Solution:

# @return a string

def minWindow(self, S, T):

minWindow = [-1,-1]

# The begin and end position (both inclusive) of current window

begin, end = -1, 0

# The number of each char in current window

totalCount = {i:0 for i in T}

# Compute the char distribution in T

need = {}

for item in T: need[item] = need.get(item, 0) + 1

# Find the first window, containing all the characters in T

needCount = len(T)

while end < len(S):

if S[end] in need:

if begin == -1: begin = end

totalCount[S[end]] += 1

if totalCount[S[end]] <= need[S[end]]:

# Find one more char for a qualified window

needCount -= 1

# Enough chars to form a window

if needCount == 0: break

end += 1

else:

# Did not find a window

return ""

# Try to minimize the window length by removing the leftmost items

while True:

if S[begin] in need:

if totalCount[S[begin]] > need[S[begin]]:

totalCount[S[begin]] -= 1

begin += 1

else:

# Already be minimum

break

else:

begin += 1

minWindow = [begin, end]

# Try next window, ending with S[begin]

while True:

# Find the next window, ending with current S[begin]

end += 1

while end < len(S):

if S[end] == S[begin]: break

if S[end] in totalCount: totalCount[S[end]] += 1

end += 1

else:

# No windows left.

break

# Minimize current window, by removing the leftmost items

begin += 1

while begin <= end:

if S[begin] in need:

if totalCount[S[begin]] > need[S[begin]]:

totalCount[S[begin]] -= 1

begin += 1

else:

# Minimized

break

else:

begin += 1

if end - begin < minWindow[1] - minWindow[0]:

# Find a shorter window

minWindow[0], minWindow[1] = begin, end

return S[minWindow[0]: minWindow[1]+1]

Solution to Sort Colors by LeetCode

17 Jun

Question: https://oj.leetcode.com/problems/sort-colors/ Question Name: Sort Colors

class Solution:

# @param A a list of integers

# @return nothing, sort in place

def sortColors(self, A):

''' The one-pass solution is similar with the 3-way

quick sort algorithm.

'''

nextZero = 0 # The position to store the next 0

nextTwo = len(A) - 1 # The position to store the next 2

index = 0

while index <= nextTwo: # !!! BEWARE OF THE RANGE !!!

if A[index] == 0: # May need to be moved to the head.

if index == nextZero:

# Already in the head part. No need to move.

index += 1

nextZero += 1

else:

# Move the the head part.

A[index], A[nextZero] = A[nextZero], A[index]

nextZero += 1

elif A[index] == 2: # Need to be moved to the tail.

A[index], A[nextTwo] = A[nextTwo], A[index]

nextTwo -= 1

else: # Keep in the middle range.

index += 1

return

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...