Frontend School

Count Transaction Streaks

DSA
medium

Count Transaction Streaks

Medium
Arrays
Hashing

Overview

At Flipkart, understanding customer purchasing patterns is crucial for optimizing product recommendations and targeted promotions. One such pattern involves identifying 'transaction streaks' — consecutive sequences of purchases whose total value matches a specific target. This problem asks you to analyze a list of individual transaction values to find how many such streaks exist.

What you need to do / Task

Given an array transactions representing the monetary values of a series of individual customer transactions, and a targetSum, your task is to implement a function that returns the total number of contiguous subarrays (transaction streaks) within transactions whose elements sum up to exactly targetSum.

Input & output

  • Input:
    • transactions: An array of numbers (number[]), where each element transactions[i] represents the value of an individual transaction.
    • targetSum: A number (number), representing the desired sum for a transaction streak.
  • Output:
    • A single number (number), which is the total count of contiguous subarrays in transactions that sum up to targetSum.

Clarifications

  • Empty transactions array: If the transactions array is empty, no subarrays can be formed, so the function should return 0.
  • Negative transaction values: Transaction values can be negative (e.g., refunds or adjustments). Your solution should handle these correctly.
  • targetSum can be zero: The target sum itself can be zero. This should also be handled correctly, especially in arrays containing zero values.
  • Large inputs: Consider the performance implications for arrays up to 20,000 elements.

Examples

1

Example 1

Input:

transactions = [1, 2, 3, -1, 4], targetSum = 5

Output:

2

Note:

The subarrays that sum to 5 are: [2, 3] (elements at index 1 and 2) and [1, 2, 3, -1] (elements at index 0 to 3).

2

Example 2

Input:

transactions = [1, 1, 1], targetSum = 2

Output:

2

Note:

The subarrays that sum to 2 are: [1, 1] (first two elements) and [1, 1] (last two elements).

3

Example 3

Input:

transactions = [0, 0, 0], targetSum = 0

Output:

6

Note:

All possible contiguous subarrays sum to 0: [0] (3 times), [0, 0] (2 times), and [0, 0, 0] (1 time). Total 3 + 2 + 1 = 6.

Constraints

Constraints & assumptions

  • 1 <= transactions.length <= 2 * 10^4
  • -1000 <= transactions[i] <= 1000
  • -10^7 <= targetSum <= 10^7
  • The solution should aim for optimal time complexity, ideally O(N), where N is the length of transactions.
  • Space complexity should be reasonable, ideally O(N) at most.

What interviewers evaluate

  • Algorithmic Correctness: Does the solution correctly identify all subarrays summing to targetSum?
  • Efficiency: Is the chosen algorithm performant enough for the given constraints (time and space complexity)?
  • Edge Case Handling: Does the code gracefully handle scenarios like empty arrays, negative numbers, or targetSum being zero?
  • Code Quality: Is the code clean, readable, well-structured, and easy to understand?

Loading editor...