Search in Rotated Sorted Array

Binary Search · Medium · Week 12 · Phase 4

Day 80 — Search in Rotated Sorted Array

Coding problem

Problem	Search in Rotated Sorted Array
LeetCode ID(s)	LeetCode #33
Difficulty	Medium
Pattern	Binary Search
Company tags	Google
Suggested time	20m

Solution outline (coding)

Focus on the Binary Search pattern. Start by writing out a few examples by hand, then identify the invariant you must maintain (e.g., prefix sums, window bounds, visited set, heap ordering). Aim for an implementation you can explain in under a minute, including time and space complexity.

Show Python solution

# Solution template based on the main pattern for this day.
# Replace this with your final, production-ready solution as you practice.

SQL question

rotated_arrays(id, arr). BigQuery: with arrays stored as ARRAY<INT64>, implement search for a value using UDF and record latency by array length.

How to approach (SQL)

Break the prompt into steps:

Identify source tables, required joins, and filters (especially on time partitions).
Decide where you need GROUP BY vs. window functions (e.g., ROW_NUMBER, SUM() OVER, COUNT() OVER).
For BigQuery, think about partitioning and clustering to avoid unnecessary full scans.
Write the query in stages (CTEs) so each step is easy to debug and reason about. Finish by checking edge cases: nulls, late events, duplicated keys, and extreme values.