RETURN AN ARRAY WHERE EACH SLOT HOLDS THE PRODUCT OF EVERY OTHER NUMBER, USING NO DIVISION. SWEEP LEFT TO PLANT EACH PREFIX, THEN SWEEP RIGHT MULTIPLYING IN EACH SUFFIX.
EACH SLOT IS EVERYTHING TO ITS LEFT TIMES EVERYTHING TO ITS RIGHT. BUILD BOTH RUNNING PRODUCTS WITHOUT EVER DIVIDING.
TWO SWEEPS ON ONE ROW. LEFT TO RIGHT PLANTS EACH PREFIX, RIGHT TO LEFT MULTIPLIES IN THE SUFFIX. THE GOLD TILES ARE THE ANSWER.
1def product_except_self(nums):2 res = [1] * len(nums)3 prefix = 14 for i in range(len(nums)):5 res[i] = prefix6 prefix *= nums[i]7 suffix = 18 for i in range(len(nums) - 1, -1, -1):9 res[i] *= suffix10 suffix *= nums[i]11 return res
TWO WALKS DOWN THE LIST, ONE EACH WAY. STILL LINEAR.
ONLY TWO RUNNING NUMBERS, PREFIX AND SUFFIX. THE REGISTER TILE SHOWS WHICHEVER IS IN PLAY. THE OUTPUT ARRAY DOES NOT COUNT.