Coding Questions - Arrays

This page will collect all the array related questions.

Binary Search

There’re 2 ways to implement the simplest binary search on a sorted array:

def binary_search(nums, lo, hi, target):
    if lo > hi:
        return lo
    mid = (lo+hi)>>1
    if nums[mid] == target:
        return mid
    else:
        return binary_search(nums, mid+1, hi, target) if nums[mid] < target else binary_search(nums, lo, mid-1, target)


def binary_search_stack(nums, target):
    lo, hi = 0, len(nums)-1
    while lo < hi: # since it's array, we don't need to use while True to keep it loop
        mid = (lo+hi)>>1
        if nums[mid] == target:
            lo = mid
            break
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return lo

LeetCode 189. Rotate Array

After i tried so many different solutions, i can’t believe the real answer is so simple.

My initial solution with failures:

class Solution(object):
    def rotate(self, nums, k):
        # Swap the last k elements with the first k elements.
        # The last k elements will be in the correct positions
        # but we need to rotate the remaining (n - k) elements
        # to the right by k steps.
        k = k%len(nums)
        def helper(nums, k):
            for i in range(k):
                nums[i], nums[len(nums)-k+i] = nums[len(nums)-k+i], nums[i]
            for i in range(k):
                start = k+i
                end = len(nums)-k+i
                for j in range(end, start, -1):
                    nums[j], nums[j-1] = nums[j-1], nums[j]
        if k < len(nums)/2:
            helper(nums, k)
        else:
            nums = nums[len(nums)/2:] + nums[:len(nums)/2]
            for i in range(k-len(nums)/2):
                for j in range(len(nums)-1):
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]

The expected solution:

class Solution(object):
    def rotate(self, nums, k):
        def reverseInPlace(nums, start, end):
            while start<end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

        k = k % len(nums)
        reverseInPlace(nums, 0, len(nums)-1)
        reverseInPlace(nums, 0, k-1)
        reverseInPlace(nums, k, len(nums)-1)

Tip: 1. 2 pointers can accelerate the search on a sorted array.