Katkat
Back

Find index with positive suffix sums

LinkedInData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize array traversals using prefix or suffix sums, specifically evaluating your skill in calculating cumulative values efficiently in O(n) time.

Problem Statement

Given an integer array nums, find all indices i such that the sum of all elements from index i to the end of the array is strictly greater than 0. Return these indices in increasing order.

Function Signature

def find_positive_suffix_indices(nums: List[int]) -> List[int]:

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Examples

Example 1:

  • Input: nums = [1, -2, 3, 0]
  • Suffix sums:
    • index 3: 0 (sum: 0)
    • index 2: 3 + 0 = 3 (sum: 3)
    • index 1: -2 + 3 + 0 = 1 (sum: 1)
    • index 0: 1 - 2 + 3 + 0 = 2 (sum: 2)
  • Output: [0, 1, 2]
  • Explanation: Suffix sums are [2, 1, 3, 0]. Indices 0, 1, and 2 have suffix sums > 0.

Example 2:

  • Input: nums = [5, -10, 2]
  • Suffix sums: [5 + -10 + 2, -10 + 2, 2] = [-3, -8, 2]
  • Output: [2]

Edge Cases

  • Array containing all negative numbers.
  • Array containing zeros.
  • Single element array.

Hints

Hint 1

Instead of calculating the sum from scratch for every index (which leads to O(n^2)), consider calculating the sums in reverse.

Hint 2

A suffix sum at index `i` is simply `nums[i] + suffix_sum_at_i_plus_1`.

Hint 3

Iterate through the array from the last index to the first, maintaining a running total of the sum encountered so far.

Follow-up questions

  • What is the time and space complexity of your solution?
  • How would your approach change if you needed to find the index with the *largest* suffix sum?
  • If the array were modified in real-time, how would you maintain the suffix sums efficiently?