Array Manipulation

  • + 0 comments
    def arrayManipulation(n, queries):
        """Finds the maximum value in an array after multiple range updates.
    
        Uses a difference array to efficiently track changes.
    
        Args:
            n (int): Array size.
            queries (list of list): List of [start, end, value] updates.
    
        Returns:
            int: Maximum value after all updates.
        """
    
        diff = [0] * (n + 2)  # Difference array (1-indexed with extra cell)
    
        for start, end, value in queries:
            diff[start] += value  # Increase at start
            diff[end + 1] -= value  # Cancel effect after end
    
        max_num = 0  # Track maximum value
        curr_sum = 0  # Track current prefix sum
        for i in range(1, n + 1):
            if diff[i] == 0:  # Skip if no change
                continue
            curr_sum += diff[i]  # Update prefix sum
            max_num = max(max_num, curr_sum)  # Update maximum
    
        return max_num