2221. Find Triangular Sum of an Array

MediumArrayMathCombinatoricsSimulation
Leetcode Link

Problem Description

The problem presents us with an integer array nums with each element being a digit from 0 to 9. We need to compute what is called the "triangular sum" of this array.

To find the triangular sum, we repeatedly perform the following process:

  1. Check if the array nums has only one element. If yes, the process ends, and this element is our triangular sum.
  2. If the array has more than one element, we create a new array newNums that has one less element than nums.
  3. We then populate newNums such that each element at index i is equal to (nums[i] + nums[i+1]) % 10. This is the sum of consecutive elements in the original array modulo 10.
  4. We replace nums with newNums and repeat the process from step 1.

Our goal is to keep repeating this process until there is only one element left in nums, which will be our answer.

Intuition

The solution is based on iterative reduction. Notice that in each iteration, the array size is reduced by 1. This process continues until only one element remains. Our task is to simulate this process programmatically.

The approach avoids creating multiple arrays for each iteration by continually updating the original array, which is both space-efficient and direct. It leverages in-place updates for nums, each time updating the element at index j based on the element at j and j + 1.

We initiate this process from the first element (index 0) to the second last element (n - 2) of the current iteration's array size, and afterward, we reduce our array size (n) by 1. This process is repeated until we reach the array size of 1, and this final single element is the triangular sum of the original array.

Learn more about Math and Combinatorics patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The reference solution code provided demonstrates the implementation of the intuitive approach we discussed earlier. It utlizes a nested loop to successively reduce the array and calculate the new values.

Here's a step-by-step breakdown of the algorithm applied in the solution code:

  1. Determine the length of the nums array and store it in the variable n.
  2. Start an outer loop to iteratively reduce the size of the nums array. This loop runs from the current size n down to 1.
  3. Inside the outer loop, there's an inner loop which is where the actual update takes place. This loop runs from 0 to i - 1, where i is the current size of the nums array for that iteration.
  4. Within the inner loop, calculate the new value for nums[j] as (nums[j] + nums[j + 1]) % 10. This formula is applied to every pair of adjacent elements, effectively shifting the entire nums array by one position to the left.
  5. When the outer loop finishes (which is when the array size n reaches 1), we have our triangular sum stored in nums[0], and we return this value as the triangular sum of the array.

The data structure used here is just the initial integer array nums, and we are manipulating it in place to maintain space efficiency. No auxiliary data structures are used.

The pattern followed is iterative reduction combined with in-place updates, which is a common way to deal with problems where the size of the data structure changes in each iteration based on specific calculation rules.

Here is the core part of the solution code that aligns with the description above:

1n = len(nums)
2for i in range(n, 0, -1):
3    for j in range(i - 1):
4        nums[j] = (nums[j] + nums[j + 1]) % 10
5return nums[0]

As seen, the outer loop runs until the array is reduced to a single element, and the inner loop makes the required modifications to the nums array based on the transition rule (nums[i] + nums[i+1]) % 10.

This approach is both clean and efficient, allowing for easy understanding and avoiding any unnecessary space complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following uses divide and conquer strategy?

Example Walkthrough

Let's take a small example to illustrate the solution approach. Suppose nums is [1, 2, 3, 4, 5]. We need to apply the solution approach to this input to find the triangular sum.

  1. n = len(nums) will set n to be 5 since there are five elements in the input array.

  2. We then enter the outer loop, which will continue until n is reduced to 1.

  3. The first iteration of the outer loop will not change n, but will initiate the inner loop which runs n-1 times (4 times in this case).

  4. In the inner loop for this iteration, we update nums as follows:

    • nums[0] becomes (1 + 2) % 10 = 3
    • nums[1] becomes (2 + 3) % 10 = 5
    • nums[2] becomes (3 + 4) % 10 = 7
    • nums[3] becomes (4 + 5) % 10 = 9 Now, nums looks like [3, 5, 7, 9].

  5. For the next iteration of the outer loop, we decrement n to 4 and run the inner loop again to update nums:

    • nums[0] becomes (3 + 5) % 10 = 8
    • nums[1] becomes (5 + 7) % 10 = 2
    • nums[2] becomes (7 + 9) % 10 = 6 Now, nums looks like [8, 2, 6].

  6. With n now at 3, the outer loop iterates and the inner loop continues updates:

    • nums[0] becomes (8 + 2) % 10 = 0
    • nums[1] becomes (2 + 6) % 10 = 8 Now, nums looks like [0, 8].

  7. Lastly, with n at 2, we run the inner loop one more time:

    • nums[0] becomes (0 + 8) % 10 = 8 Now nums is simply [8].

  8. When we exit the outer loop, we return nums[0], which is 8. This is the triangular sum of the array [1, 2, 3, 4, 5].

Following the problem's strategy, we successfully computed the triangular sum by iteratively reducing the array and updating it in place without any extra space. The final answer is 8.

Solution Implementation

1# Import the typing module to define the type of input.
2from typing import List
3
4class Solution:
5    def triangular_sum(self, nums: List[int]) -> int:
6        """
7        Calculate the triangular sum of a list of integers.
8        The triangular sum of a list of integers is obtained by the following process:
9        - Replace each element by the sum of itself and the next element, modulo 10.
10        - Repeat the process until only one number remains.
11      
12        Args:
13        nums (List[int]): A list of integers between 0 and 9 inclusive.
14      
15        Returns:
16        int: The final integer (between 0 to 9) after the process is done.
17        """
18        # Get the initial length of nums
19        n = len(nums)
20      
21        # Loop from the length of nums down to 1
22        for i in range(n, 0, -1):
23            # Calculate the new values for the triangular sum step
24            for j in range(i - 1):
25                # Update each element with the sum of itself and the next element, mod 10
26                nums[j] = (nums[j] + nums[j + 1]) % 10
27      
28        # The first element of the list is the answer after the process
29        return nums[0]
30
31# Note: The method name has been changed to 'triangular_sum' to match the Python naming convention.
32# All variable names are already properly named, and no method names have been altered.
33
1class Solution {
2    public int triangularSum(int[] nums) {
3        // Find the length of the input array.
4        int n = nums.length;
5
6        // Outer loop to reduce the array size by 1 in each iteration.
7        // Note that it should be 'i > 0' rather than 'i >= 0' 
8        // since we want to stop when we reach the last element.
9        for (int i = n; i > 0; --i) {
10            // Inner loop to iterate through the elements up to the new size.
11            for (int j = 0; j < i - 1; ++j) {
12                // Update the current element by adding it to the next element.
13                // The sum is modulo 10 as per the problem's requirement.
14                nums[j] = (nums[j] + nums[j + 1]) % 10;
15            }
16        }
17      
18        // After reducing the array to a single element, return that element.
19        return nums[0];
20    }
21}
22
1#include <vector> // Include the header for using vectors
2
3class Solution {
4public:
5    int triangularSum(std::vector<int>& nums) {
6        // Get the size of the input vector `nums`
7        int size = nums.size();
8      
9        // Start from the last row and move upwards, considering each row
10        for (int row = size; row > 0; --row) {
11            // Iterate through each element up to the second-to-last of the current row
12            for (int col = 0; col < row - 1; ++col) {
13                // Update the current element by adding it with the next element,
14                // and apply modulo 10 to the result
15                nums[col] = (nums[col] + nums[col + 1]) % 10;
16            }
17        }
18      
19        // After processing all rows, the first element of the vector contains the result
20        return nums[0];
21    }
22};
23
1// Import the array utility module
2import { array } from 'util';
3
4// Function that calculates the triangular sum of an array of numbers
5function triangularSum(nums: number[]): number {
6    // Get the length of the input array `nums`
7    let size: number = nums.length;
8  
9    // Start from the last row and move upwards, considering each row
10    for (let row = size; row > 0; --row) {
11        // Iterate through each element up to the second-to-last of the current row
12        for (let col = 0; col < row - 1; ++col) {
13            // Update the current element by adding it with the next element,
14            // and apply modulo 10 to the result
15            nums[col] = (nums[col] + nums[col + 1]) % 10;
16        }
17    }
18  
19    // After processing all rows, the first element of the array contains the triangular sum
20    return nums[0];
21}
22
23// Sample usage of the function
24const sampleArray: number[] = [1, 2, 3, 4, 5];
25const result: number = triangularSum(sampleArray);
26console.log(`The triangular sum is: ${result}`);
27
Not Sure What to Study? Take the 2-min Quiz：

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Time and Space Complexity

The time complexity of the provided code can be analyzed as follows:

We have a nested loop where the outer loop runs n times (where n is the length of nums) and the inner loop performs i - 1 iterations, where i decreases from n to 1. This creates a triangular number of operations (hence the name "triangularSum"). The total number of operations can be calculated by the sum of the first n integers which is (n * (n + 1)) / 2. Consequently, removing the non-dominant terms and constants, we can describe the time complexity as O(n^2).

The space complexity of the code can be determined as follows:

The solution modifies the input list nums in-place and does not use any additional space that grows with the input size (other than a constant amount of space for the loop indices and the variable n). Hence, the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫