Array, LeetCode
To calculate the middle index: use (left + right) // 2, where // denotes floor division. When the number of elements is even, the fomular returns the left-middle index.
Optimization: left + (right - left) // 2 - Avoid integer overflow caused by a too large right + left through interval offset
Why O(log(n))?
- Each iteration eliminates half of elements
- Search Space shrinks exponentially
- 1st iteration: n elements
- 2st iteration: n/2 elements
- At most log(n) comparisons are needed
- 2^k = n, log(n) = k
- Stop in advance (
nums[middle] == target) before checking all search space (left == right)
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
middle = left + (right - left)//2
if target < nums[middle]:
# target is smaller, search the left half and update the right boundary
right = middle - 1
elif target > nums[middle]:
# target is bigger, search the right half and update the left boundary
left = middle + 1
else:
return middle
return -1
Run test cases:
a = [1, 2, 3]
b = [2, 3, 4]
for i in range(len(a)):
assert a[i] == b[i] # assertion error
The algorithm aims to remove elements. Using nums[j] == val finds elements to delete, but deletion is essentially “doing nothing”. The elements that actually need operations are those where nums[j] != val (preserve and move postions)
from typing import List
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow = 0
for fast in range(len(nums)):
if nums[fast] != val: # we need to do some operations
nums[slow] == nums[fast]
slow += 1
return slow
977. Squares of a Sorted Array
# left, right pointers:
left = 0
right = len(nums) - 1
while left <= right:
# dynamic boundaries
# last iteration: left == right (can terminate early)
# slow, fast pointers:
slow = 0
for fast in range(len(nums)):
# complete traversal (counldn't terminate early)
In-place: algorithms that do not use additional data structures to stroe data during execution, but instead modify the original input data structure directly.
Space Complexity:
- In-place: O(1)
- Not in-place: O(n), additional array
Why not in-place in this question?
- Position changes are very complex (lacking a fixed direction or fixed pattern). Cross movements are difficult to accomplish with simple (two) pointer opertaions
from typing import List
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
left = 0
right = len(nums) - 1
result = [0] * len(nums)
position = len(nums) - 1
while left <= right:
left_square = nums[left] ** 2
right_square = nums[right] ** 2
if left_square <= right_square: # write '<' first, then check whether '=' works
result[position] = right_square
position -= 1
right -= 1
else:
reslut[position] = left_square
position -= 1
left += 1
return result
209. Minimum Size Subarray Sum
In a loop (e.g., while, for):
- record the current valid result first
- update the state
while sum_of_subarray >= target: min_length = max(min_length, fast - slow + 1) # record min_length sum_of_subarray -= nums[slow] # update the sum_of_subarray # record nums[slow] based on slow first slow += 1 # update slow # use it, and then update it
right - left actually calculates the length of the interval [left, right)
from typing import List
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_length = float('inf')
sub_of_subarray = 0
slow = 0
for fast in range(len(nums)):
sub_of_subarray += nums[fast]
while sub_of_subarray >= target:
min_length = max(min_length, fast - slow + 1)
sum_of_array -= nums[slow]
slow += 1
return min_length if min_length != float('inf') else 0
for _ in range(n): iterates n times
for _ in range(left, right): iterates right - left times -> [left, right)
for _ in range(left, right, -1): iterates abs(right - left) times -> (right, left]
n * n matrix: every row, every column has n elements
[0] * n: has n elements in total
from typing import List
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix = [[0] * n for _ in range(n)]
left = 0
right = n - 1
top = 0
bottom = n - 1
count = 1
while left <= right and top <= bottom:
for i in range(left, right + 1):
matrix[top][i] = count
count += 1
top += 1 # update the boundary when all elemenets in a certain row/column is handled
if top > bottom:
break
for i in range(top, bottom + 1):
matrix[i][right] = count
count += 1
right -= 1
if left > right:
break
for i in range(right, left - 1, -1):
matrix[bottom][i] = count
count += 1
bottom -= 1
if top > bottom:
break
for i in range(bottom, top - 1, -1):
matrix[i][left] = count
count += 1
left += 1
if left > right:
break
return matrix
"""
prefix_sum
nums = [1, 2, 3]
prefix_sum = [0, 1, 3, 6]
prefix_sum[i] = nums[0] + ... nums[i - 1]
prefix_sum[j + 1] = nums[0] + ... nums[i - 1] + nums[i] + ... + nums[j]
prefix_sum[j + 1] - prefix_sum[i] = nums[i] + ... nums[j]
"""
prefix_sum =[0]
for num in nums:
prefix_sum.append(prefix_sum[-1] + num)
# sum of interval [i, j] could be represented as prefix_sum[j + 1] - prefix_sum[i]
Enjoy Reading This Article?
Here are some more articles you might like to read next: