Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You may assume no duplicate exists in the array.
In [4]:
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums is None or len(nums) == 0:
return -1
start, end = 0, len(nums)-1
x = nums[-1]
while start + 1 < end:
mid = start + (end - start) / 2
if nums[mid] <= x:
end = mid
else:
start = mid
return nums[start] if nums[start] < nums[end] else nums[end]
In [5]:
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums is None or len(nums) == 0:
return -1
start, end = 0, len(nums)-1
while start < end:
mid = start + (end - start) / 2
if nums[mid] > nums[end]:
start = mid + 1
else:
end = mid
return nums[start]
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
In [7]:
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if nums is None or n == 0:
return -1
start, end = 0, n-1
while start + 1 < end:
mid = start + (end - start) / 2
if nums[mid] == nums[end]:
end -= 1 ## pretty smart and simple!!
elif nums[mid] > nums[end]:
start = mid
else:
end = mid
return nums[start] if nums[start] <= nums[end] else nums[end]
You are given a target value to search. If found in the array return its index, otherwise return -1.
https://leetcode.com/problems/search-in-rotated-sorted-array/#/description
In [6]:
# trival way
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
n = len(nums)
if nums is None or n == 0:
return -1
# find the minimun index
start, end = 0, n-1
while start < end:
mid = start + (end - start) / 2
if nums[mid] > nums[end]:
start = mid + 1
else:
end = mid
mark = start
# binary search
start, end = 0, n-1
while start + 1 < end:
mid = start + (end - start) / 2
realmid = (mid + mark) % n
if nums[realmid] == target:
return realmid ## important !!
elif nums[realmid] < target:
start = mid + 1
else:
end = mid - 1
if nums[(start + mark) % n] == target:
return (start + mark) % n
if nums[(end + mark) % n] == target:
return (end + mark) % n
return -1
In [8]:
# good way: beats 96.13% key of bisection: shirink the interval !!
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
n = len(nums)
if nums is None or n == 0:
return -1
# binary search
start, end = 0, n-1
while start + 1 < end:
mid = start + (end - start) / 2
if nums[mid] == target:
return mid
elif nums[mid] > nums[end]:
if nums[end] < target < nums[mid]:
end = mid - 1
else:
start = mid
else:
if nums[mid] < target <= nums[end]:
start = mid + 1
else:
end = mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
In [9]:
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
if nums is None or len(nums) == 0:
return False
start, end = 0, len(nums)-1
while start + 1 < end:
mid = start + (end - start) / 2
if nums[mid] == target:
return True
if nums[mid] == nums[end]:
end -= 1
elif nums[mid] > nums[end]:
if nums[end] < target < nums[mid]:
end = mid - 1
else:
start = mid
else:
if nums[mid] < target <= nums[end]:
start = mid + 1
else:
end = mid
return True if nums[start] == target or nums[end] == target else False
Given a rotated sorted array, recover it to sorted array in-place.
Example [4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]
In [15]:
class Solution:
"""
@param nums: The rotated sorted array
@return: nothing
"""
def recoverRotatedSortedArray(self, nums):
# write your code here
def rev(nums, start, end):
for i in range((end - start) / 2 + 1):
nums[start+i], nums[end-i] = nums[end-i], nums[start+i]
n = len(nums)
for i in range(n-1):
if nums[i] > nums[i+1]:
rev(nums, 0, i)
rev(nums, i+1, n-1)
rev(nums, 0, n-1)
break
Given a string and an offset, rotate string by offset. (rotate from left to right)
Given "abcdefg".
offset=0 => "abcdefg" offset=1 => "gabcdef" offset=2 => "fgabcde" offset=3 => "efgabcd"
In [19]:
class Solution:
# @param s: a list of char
# @param offset: an integer
# @return: nothing
def rotateString(self, s, offset):
# write you code here
def rev(s, start, end):
for i in range((end - start) / 2 + 1):
s[start+i], s[end-i] = s[end-i], s[start+i]
if s is not None and len(s) > 0:
n = len(s)
offset %= n
if 0 < offset < n-1:
rev(s, 0, n - offset - 1)
rev(s, n - offset, n - 1)
rev(s, 0, n-1)
elif offset == n-1:
rev(s, 0 , n-1)
Write an efficient algorithm with O(m + n) that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.
In [10]:
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or len(matrix) == 0:
return False
if len(matrix[0]) == 0:
return False
m, n = len(matrix), len(matrix[0])
# O(m + n) brilliant
r, c = 0, n-1
while r <= m-1 and c >= 0:
if matrix[r][c] == target:
return True
elif matrix[r][c] > target:
c -= 1
else:
r += 1
return False
# O(mlogn), straight forward
for i in range(m):
if matrix[i][0] <= target <= matrix[i][-1]:
start, end = 0, n-1
while start + 1 < end:
mid = start + (end - start) / 2
if matrix[i][mid] == target:
return True
elif matrix[i][mid] < target:
start = mid + 1
else:
end = mid - 1
if matrix[i][start] == target or matrix[i][end] == target:
return True
return False
In [20]:
class Solution(object):
def minArea(self, image, x, y):
"""
:type image: List[List[str]]
:type x: int
:type y: int
:rtype: int
"""
def isBlackCol(image, col):
for i in range(len(image)):
if image[i][col] == '1':
return True
return False
def isBlackRow(image, row):
for j in range(len(image[row])):
if image[row][j] == '1':
return True
return False
if image is None or len(image) == 0:
return 0
m, n = len(image), len(image[0])
# left
start, end = 0, y
while start + 1 < end:
mid = start + (end - start) / 2
if isBlackCol(image, mid):
end = mid
else:
start = mid
if isBlackCol(image, start):
left = start
else:
left = end
# right
start, end = y, n-1
while start + 1 < end:
mid = start + (end - start) / 2
if isBlackCol(image, mid):
start = mid
else:
end = mid
if isBlackCol(image, end):
right = end
else:
right = start
# up
start, end = 0, x
while start + 1 < end:
mid = start + (end - start) / 2
if isBlackRow(image, mid):
end = mid
else:
start = mid
if isBlackRow(image, start):
up = start
else:
up = end
# bottom
start, end = x, m-1
while start + 1 < end:
mid = start + (end - start) / 2
if isBlackRow(image, mid):
start = mid
else:
end = mid
if isBlackRow(image, end):
bottom = end
else:
bottom = start
return (right - left + 1) * (bottom - up + 1)
Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.
Example Given nums = [1, 2, 4, 8, 6, 3] return 8 Given nums = [10, 9, 8, 7], return 10
https://www.lintcode.com/en/problem/maximum-number-in-mountain-sequence/#
In [11]:
class Solution:
# @param {int[]} nums a mountain sequence which increase firstly and then decrease
# @return {int} then mountain top
def mountainSequence(self, nums):
# Write your code here
if nums is None or len(nums) == 0:
return -1
n = len(nums)
if n <= 2:
return max(nums)
start, end = 0, n-1
while start + 1 < end:
mid = start + (end - start) / 2
if 0 < mid < n-1:
if nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1]:
return nums[mid]
elif nums[mid] <= nums[mid-1]:
end = mid - 1
else:
start = mid + 1
return nums[start] if nums[start] > nums[end] else nums[end]
In [12]:
class Solution:
# @param {int[]} nums a mountain sequence which increase firstly and then decrease
# @return {int} then mountain top
def mountainSequence(self, nums):
# Write your code here
left, right = 0, len(nums) - 1
while left + 1 < right:
m1 = left + (right - left) / 2
m2 = right - (right - m1) / 2
if nums[m1] < nums[m2]:
left = m1 + 1
elif nums[m1] > nums[m2]:
right = m2 - 1
else:
left = m1
right = m2
return max(nums[left], nums[right])
https://leetcode.com/problems/find-peak-element/#/description
In [13]:
class Solution(object):
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums is None or len(nums) == 0:
return -1
n = len(nums)
if n == 1:
return 0
start, end = 0, n-1
while start + 1 < end:
mid = start + (end - start) / 2
if nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1]:
return mid
elif nums[mid] < nums[mid+1]:
start = mid
else:
end = mid
return start if nums[start] > nums[end] else end
Four steps:
• start + 1 < end
• start + (end - start) / 2
• A[mid] ==, <, >
• A[start] A[end] ? target
Corner cases:
if nums is None or len(nums) == 0: return -1
Tricks:
compare with nums[start] or nums[end] for the rotated arrays
by setting mid = start + (end - start) / 2, mid + 1 should be in the range
In [ ]:
# reverse
def rev(nums, start, end):
for i in range((end - start) / 2 + 1):
nums[start+i], nums[end-i] = nums[end-i], nums[start+i]