Frontend School

High-Value Transaction Zones

DSA
medium

High-Value Transaction Zones

Medium
Matrix
BFS
DFS

Overview

At Stripe, ensuring the integrity and security of financial transactions is paramount. A key part of this involves identifying unusual patterns or concentrations of high-value transactions that might indicate potential risks or anomalies. This problem challenges you to develop an algorithm that can detect and analyze "high-value transaction zones" within a grid representing transaction values.

What you need to do / Task

You are given a 2D grid, grid, where each cell (r, c) contains a numerical value representing a transaction amount. You are also given a threshold value. Your task is to identify and analyze "high-value transaction zones". A high-value transaction zone is defined as a group of 4-directionally connected cells where each cell's transaction value is strictly greater than the given threshold.

Your function should return an array [numberOfZones, maxZoneValue], where:

  1. numberOfZones is the total count of distinct high-value transaction zones found in the grid.
  2. maxZoneValue is the maximum sum of transaction values found within any single high-value transaction zone. If no zones are found, maxZoneValue should be 0.

Input & output

Input:

  • grid: number[][] - A 2D array of integers representing transaction values. grid[r][c] is the transaction value at row r and column c.
  • threshold: number - An integer value. Transactions strictly greater than this threshold are considered "high-value".

Output:

  • [number, number] - An array containing two integers:
    • The first element is the total count of distinct high-value transaction zones.
    • The second element is the maximum sum of transaction values of any single high-value transaction zone.

Clarifications

  • Connectivity: Cells are considered connected if they are adjacent horizontally or vertically (4-directionally). Diagonal connections do not count.
  • Zone Definition: A cell (r, c) is part of a high-value transaction zone if grid[r][c] > threshold. All cells within a zone must satisfy this condition.
  • Distinct Zones: Two zones are distinct if they are not connected to each other.
  • No Zones: If no high-value transaction zones are found, the function should return [0, 0].

Examples

1

Example 1

Input:

grid = [[10, 5, 20], [15, 2, 30], [8, 12, 25]], threshold = 10

Output:

[3,75]

Note:

Cells strictly greater than 10 are: (0,2)=20, (1,0)=15, (1,2)=30, (2,1)=12, (2,2)=25. Zone 1: (0,2)=20, (1,2)=30, (2,2)=25. Sum = 75. Zone 2: (1,0)=15. Sum = 15. Zone 3: (2,1)=12. Sum = 12. Total 3 zones. Maximum sum is 75.

2

Example 2

Input:

grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], threshold = 10

Output:

[0,0]

Note:

No transaction values are strictly greater than 10. Thus, no high-value transaction zones are found.

3

Example 3

Input:

grid = [[50, 50], [50, 50]], threshold = 40

Output:

[1,200]

Note:

All cells (50, 50, 50, 50) are strictly greater than 40 and are 4-directionally connected. They form a single zone with a total sum of 200.

Constraints

Constraints & assumptions

  • 1 <= grid.length, grid[0].length <= 200 (The grid will have at least one row and one column).
  • 0 <= grid[r][c] <= 10^9 (Transaction values are non-negative).
  • 0 <= threshold <= 10^9
  • The input grid will always be a valid 2D array (not jagged).

Out of scope

  • Handling non-integer transaction values or threshold.
  • Optimizations for extremely sparse or dense grids beyond standard graph traversal.

What interviewers evaluate

  • Correctness: The solution accurately identifies all distinct high-value transaction zones and calculates their maximum sum, handling all specified conditions and edge cases.
  • Algorithm Design: The chosen approach is efficient (optimal time/space complexity) and appropriate for the problem constraints.
  • Code Quality: The code is well-structured, readable, maintainable, and adheres to good programming practices.
  • Test Case Consideration: The candidate demonstrates an understanding of how to test the solution and considers various input scenarios.

Loading editor...