Space
Open
From Fieldwork
Scales
Archive
I'm just putting this here for posterity. We should expect to not see this, but there're a lot of thoughts I've been having about the essence of programming, and what it means to seek truth.
I've found that two axes can relatively nicely distil what I've been thinking:
We want to reduce ambiguity — this means exhaustively mapping out the cases. Following the implicit structure and making it explicit, or imposing a known algorithm or structure to make a problem conform to a known solution.
We want to reduce complexity — this comes in the form of identifying places where we can make use of simplicity. What's true is often more simple, relatively speaking.
class Solution:
def countRangeSum(self, nums: list[int], lower: int, upper: int) -> int:
# Step 1: Generate Prefix Sums
# prefix_sums[i] is the sum of nums[0...i-1]
# We include 0 to handle ranges starting from the very first element
S = [0]
for x in nums:
S.append(S[-1] + x)
def count_while_sorting(left, right):
if right - left <= 1:
return 0
mid = (left + right) // 2
# Recursively count pairs in the left half and right half
count = count_while_sorting(left, mid) + count_while_sorting(mid, right)
# Step 2: The "Magic" Count Step
# For every i in the left half, find the range [j_low, j_high)
# in the right half such that lower <= S[j] - S[i] <= upper
j_low = j_high = mid
for i in range(left, mid):
while j_low < right and S[j_low] - S[i] < lower:
j_low += 1
while j_high < right and S[j_high] - S[i] <= upper:
j_high += 1
count += (j_high - j_low)
# Step 3: Standard Merge Step
# This keeps the prefix sum array sorted for the next level of recursion
S[left:right] = sorted(S[left:right])
return count
return count_while_sorting(0, len(S))Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode