algoadvance

Leetcode 3242. Design Neighbor Sum Service

Problem Statement

You have to design a service to calculate a neighbor sum in a streaming fashion. Implement the NeighborSumService class which contains the following methods:

  1. NeighborSumService(): Initializes the object, no data needs to be preserved here.
  2. void addNum(int num): Adds a number to the data structure.
  3. int getSum(int index): Returns the sum of the numbers located at positions ‘index’, ‘index-1’, and ‘index+1’ if they exist, otherwise returns the sum of the existing neighbors (e.g., if index-1 is out of bounds, it’s not included in the sum).

Clarifying Questions

  1. Q: Are the indices 0-based or 1-based? A: The indices are 0-based.
  2. Q: Is there a limit on the number of elements that can be added? A: No specific limit is provided, but you should consider typical integer limits and memory constraints.
  3. Q: What should we return if the index provided in getSum has no elements around it or out of bounds? A: Only valid neighbors should be summed. If no such neighbors exist (e.g., empty structure or inappropriate indices), return 0.

Code

import java.util.ArrayList;
import java.util.List;

public class NeighborSumService {
    private List<Integer> nums;
    
    public NeighborSumService() {
        this.nums = new ArrayList<>();
    }
    
    public void addNum(int num) {
        this.nums.add(num);
    }
    
    public int getSum(int index) {
        int sum = 0;
        if (index >= 0 && index < nums.size()) {
            sum += nums.get(index);
        }
        if (index > 0 && index - 1 < nums.size()) {
            sum += nums.get(index - 1);
        }
        if (index + 1 >= 0 && index + 1 < nums.size()) {
            sum += nums.get(index + 1);
        }
        return sum;
    }
    
    public static void main(String[] args) {
        NeighborSumService service = new NeighborSumService();
        service.addNum(1);
        service.addNum(2);
        service.addNum(3);
        System.out.println(service.getSum(1)); // Output should be 6 (1 + 2 + 3)
        System.out.println(service.getSum(0)); // Output should be 3 (1 + 2)
        System.out.println(service.getSum(2)); // Output should be 5 (3 + 2)
    }
}

Strategy

  1. Initialization (NeighborSumService): Initialize a list to store the stream of numbers.
  2. Adding a Number (addNum): Simply append the number to the list.
  3. Getting Neighbor Sum (getSum):
    • Check if the index is within the bounds.
    • Sum up the values at index, index-1, and index+1 if they exist within the list boundaries.
    • Use conditionals to ensure we add only valid neighbors.

Time Complexity

  1. addNum(int num):
    • Time Complexity: O(1)
    • Reason: Adding an element at the end of a dynamic array (ArrayList) is an O(1) operation on average.
  2. getSum(int index):
    • Time Complexity: O(1)
    • Reason: Accessing elements by index in a list is O(1), and we are accessing at most three elements.

The solution efficiently handles the requirements of the problem using an ArrayList, ensuring constant time operations for both adding numbers and retrieving the neighbor sums.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI