Rotated Sorted Array

  • Find Minimum in Rotated Sorted Array

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

Find the minimum element.

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]
  • Follow up: Find Minimum in Rotated Sorted Array II

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]
  • Search in Rotated Sorted Array

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
  • Follow up for "Search in Rotated Sorted Array":

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)

Search a 2D Matrix

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)

Maximum Number in Mountain Sequence

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])

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

Summary

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]