Solve weighted pick and product except self

Question

LeetCode 528. Random Pick with Weight LeetCode 238. Product of Array Except Self

https://leetcode.com/problems/random-pick-with-weight/description/ https://leetcode.com/problems/product-of-array-except-self/description/

Random Pick with Weight (Deterministic Core)

You are given a 0-indexed array w of positive integers, where w[i] is the weight of index i.

In the original problem (LeetCode 528), you implement pickIndex() which returns an index in [0, len(w)) with probability proportional to its weight. The standard technique is to build a prefix-sum array of the weights and, given a uniformly random integer in [1, total], binary-search for the first prefix value >= target.

To make this testable deterministically, implement that core lookup directly: given the weight array w and an integer target in the range [1, sum(w)], return the index that target lands in.

Formally, build prefix sums P[i] = w[0] + w[1] + ... + w[i]. Return the smallest index i such that target <= P[i].

Example:

  w = [2, 5, 3, 4], target = 8
  prefix = [2, 7, 10, 14]

target 8 is the first value <= P[2]=10 (P[1]=7 < 8), so return 2.

This is exactly the weighted-bucket selection a correct pickIndex performs once a random number has been drawn — verifying it confirms the prefix-sum + binary-search logic that the interview is really testing.

Constraints

• 1 <= len(w) <= 10^4
• 1 <= w[i] <= 10^5
• 1 <= target <= sum(w)

Hints

1. Convert each weight into a cumulative range. Index i 'owns' the integers (P[i-1], P[i]].
2. With prefix sums sorted ascending, finding the owning index for a target is a classic lower-bound binary search: find the first prefix value that is >= target.
3. Be careful with the binary-search boundary: use a [lo, hi] window that converges to a single index, moving lo = mid+1 only when prefix[mid] < target.

Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation (so you cannot just compute the total product and divide it out — that also fails when zeros are present).

Example:

  nums = [1, 2, 3, 4]
  answer = [24, 12, 8, 6]   (24 = 2*3*4, 12 = 1*3*4, etc.)

Example with a zero:

  nums = [-1, 1, 0, -3, 3]
  answer = [0, 0, 9, 0, 0]

Constraints

• 2 <= len(nums) <= 10^5
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums fits in a 32-bit integer.

Hints

1. answer[i] = (product of everything to the left of i) * (product of everything to the right of i). Compute these two pieces separately.
2. First pass left-to-right: store in result[i] the running product of all elements strictly before i.
3. Second pass right-to-left: multiply result[i] by a running product of all elements strictly after i. This avoids division and naturally handles zeros.