Find Triangular Sum of an Array solution and explanation
Google
9 more videos on this problem
Find Triangular Sum of an Array | 2 Approaches | Constant Space | Leetcode 2221 | codestorywithMIKcodestorywithMIK · 14:01 · 6K views
2221. Find Triangular Sum of an Array || Leetcode BiWeekly Contest 75 || Leetcode 2221Bro Coders · 5:45 · 3K views
2221. Find Triangular Sum of an Array (Leetcode Medium)Programming Live with Larry · 4:53 · 1K views
2221 Find Triangular Sum of an Array | Explanation + Java Easy Solution | Biweekly | LeetcodeLit Coder · 8:52 · 1K views
Find Triangular Sum of an Array | LeetCode 2221 | 3 Approaches ExplainedSanyam IIT Guwahati · 13:55 · 580 views
2221. Find Triangular Sum of an Array | Leetcode Daily - PythonLeetcode Daily · 6:31 · 540 views
Find Triangular Sum of an Array | LeetCode 2221 - Python (2 Solutions)impoldev · 12:31 · 279 views
Find Triangular Sum of an Array - LeetCode 2221 - Java Solutionalgobest - Computer Science · 3:40 · 260 views
2221 – Find Triangular Sum of an ArrayTechie Uday · 14:12 · 195 views
Leetcode | 2221. Find Triangular Sum of an Arrayapril mix · 12:46 · 102 views
The problem
You are given a 0-indexed integer array nums, where nums[i] is a digit between 0 and 9 (inclusive).
The triangular sum of nums is the value of the only element present in nums after the following process terminates:
- Let
numscomprise ofnelements. Ifn == 1, end the process. Otherwise, create a new 0-indexed integer arraynewNumsof lengthn - 1. - For each index
i, where0 <= i < n - 1, assign the value ofnewNums[i]as(nums[i] + nums[i+1]) % 10, where%denotes modulo operator. - Replace the array
numswithnewNums. - Repeat the entire process starting from step 1.
Return the triangular sum of nums.
Example 1:
Input: nums = [1,2,3,4,5] Output: 8 Explanation: The above diagram depicts the process from which we obtain the triangular sum of the array.
Example 2:
Input: nums = [5] Output: 5 Explanation: Since there is only one element in nums, the triangular sum is the value of that element itself.
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 9
Approach overview
Problem Overview: You start with an integer array nums. Repeatedly create a new array where each element is (nums[i] + nums[i+1]) % 10. Continue until only one element remains. That final value is the triangular sum.
Approach 1: Iterative Simulation (O(n2) time, O(1) space)
This method directly simulates the process described in the problem. Iterate over the array multiple times, and during each pass update nums[i] with (nums[i] + nums[i+1]) % 10. After the first pass the effective array length becomes n-1, then n-2, and so on until one element remains. Because each level processes almost the entire array, the total work forms a triangular pattern: (n-1) + (n-2) + ... + 1, which results in O(n^2) time. Updating values in-place keeps the extra memory at O(1). This approach is straightforward and mirrors the problem statement, making it useful for quick implementation during interviews.
The logic relies purely on sequential iteration and modular arithmetic, which makes it a classic simulation problem combined with simple array manipulation.
Approach 2: Combinatorial Formula (O(n) time, O(1) space)
The triangular construction is equivalent to building rows of Pascal's triangle. Each element in the final result can be expressed as the original element multiplied by a binomial coefficient. Specifically, the final value equals sum(nums[i] * C(n-1, i)) % 10. Instead of performing every simulation step, compute the contribution of each element directly using binomial coefficients from the (n-1)th row of Pascal's triangle.
The challenge is that the result is taken modulo 10, which is not a prime number. Efficient implementations track factors of 2 and 5 while building the binomial coefficient iteratively to maintain correct modulo arithmetic. Each coefficient can be derived from the previous one using multiplicative updates, allowing the entire row to be processed in linear time. This reduces the complexity to O(n) time and constant extra space.
This technique transforms the problem into a mathematical observation about Pascal's triangle, making it a good example of applying math and combinatorics to eliminate repeated simulation.
Recommended for interviews: Start with the iterative simulation since it follows the problem definition and demonstrates clear reasoning. Strong candidates recognize the Pascal's triangle relationship and derive the combinatorial formula, which reduces the complexity to linear time and shows deeper algorithmic insight.
Approach 1: Iterative Approach
This approach involves simulating the process step-by-step by iteratively reducing the array size as described in the problem. We repeatedly create a new array where each element is the sum of consecutive elements modulo 10, until we are left with a single element.
def triangular_sum(nums):
n = len(nums)
while n > 1:
for i in range(n - 1):
nums[i] = (nums[i] + nums[i + 1]) % 10
n -= 1
return nums[0]
nums = [1, 2, 3, 4, 5]
print(triangular_sum(nums))public class TriangularSum {
public static int triangularSum(int[] nums) {
int n = nums.length;
for (int j = n; j > 1; j--) {
for (int i = 0; i < j - 1; i++) {
nums[i] = (nums[i] + nums[i + 1]) % 10;
}
}
return nums[0];
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
System.out.println(triangularSum(nums));
}
}#include <iostream>
#include <vector>
int triangularSum(std::vector<int>& nums) {
int n = nums.size();
for (int j = n; j > 1; j--) {
for (int i = 0; i < j - 1; i++) {
nums[i] = (nums[i] + nums[i + 1]) % 10;
}
}
return nums[0];
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
std::cout << triangularSum(nums) << std::endl;
return 0;
}function triangularSum(nums) {
let n = nums.length;
while (n > 1) {
for (let i = 0; i < n - 1; i++) {
nums[i] = (nums[i] + nums[i + 1]) % 10;
}
n--;
}
return nums[0];
}
let nums = [1, 2, 3, 4, 5];
console.log(triangularSum(nums));#include <stdio.h>
int triangularSum(int* nums, int numsSize) {
while (numsSize > 1) {
for (int i = 0; i < numsSize - 1; i++) {
nums[i] = (nums[i] + nums[i + 1]) % 10;
}
numsSize--;
}
return nums[0];
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
int result = triangularSum(nums, 5);
printf("%d\n", result);
return 0;
}using System;
public class TriangularSum {
public static int TriangularSum(int[] nums) {
int n = nums.Length;
while (n > 1) {
for (int i = 0; i < n - 1; i++) {
nums[i] = (nums[i] + nums[i + 1]) % 10;
}
n--;
}
return nums[0];
}
public static void Main() {
int[] nums = {1, 2, 3, 4, 5};
Console.WriteLine(TriangularSum(nums));
}
}In this Python solution, we simulate the described process by decrementing the array, updating it in place until its length is reduced to one. The resulting number is then printed.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Combinatorial Formula
A more advanced approach is to express the result of transforming the array of length `n` into a single number using combinatorial mathematics. By recognizing pattern relationships that dictate how often each number influences the final result, you can optimize the process.
from math import comb
def triangular_sum(nums):
n = len(nums)
result = 0
for i in range(n):
result = (result + nums[i] * comb(n - 1, i)) % 10
return result
nums = [1, 2, 3, 4, 5]
print(triangular_sum(nums))public class TriangularSum {
private static long combination(int n, int k) {
if (k > n) return 0;
if (k == 0 || k == n) return 1;
long res = 1;
for (int i = 0; i < k; i++) {
res = res * (n - i) / (i + 1);
}
return res;
}
public static int triangularSum(int[] nums) {
int result = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
result = (result + nums[i] * combination(n - 1, i)) % 10;
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
System.out.println(triangularSum(nums));
}
}#include <iostream>
#include <vector>
long combination(int n, int k) {
if (k > n) return 0;
if (k == 0 || k == n) return 1;
long res = 1;
for (int i = 0; i < k; i++) {
res = res * (n - i) / (i + 1);
}
return res;
}
int triangularSum(std::vector<int>& nums) {
int result = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
result = (result + nums[i] * combination(n - 1, i)) % 10;
}
return result;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
std::cout << triangularSum(nums) << std::endl;
return 0;
}function combination(n, k) {
if (k > n) return 0;
if (k === 0 || k === n) return 1;
let res = 1;
for (let i = 0; i < k; i++) {
res = res * (n - i) / (i + 1);
}
return res;
}
function triangularSum(nums) {
let result = 0;
let n = nums.length;
for (let i = 0; i < n; i++) {
result = (result + nums[i] * combination(n - 1, i)) % 10;
}
return result;
}
let nums = [1, 2, 3, 4, 5];
console.log(triangularSum(nums));#include <stdio.h>
int combination(int n, int k) {
if (k > n) return 0;
if (k == 0 || k == n) return 1;
if (k == 1 || k == n - 1) return n;
long res = 1;
for (int i = 0; i < k; i++) {
res = res * (n - i) / (i + 1);
}
return (int)res;
}
int triangularSum(int* nums, int numsSize) {
int result = 0;
for (int i = 0; i < numsSize; i++) {
result = (result + nums[i] * combination(numsSize - 1, i)) % 10;
}
return result;
}
int main() {
int nums[] = {1, 2, 3, 4, 5};
printf("%d\n", triangularSum(nums, 5));
return 0;
}using System;
public class TriangularSum {
private static long Combination(int n, int k) {
if (k > n) return 0;
if (k == 0 || k == n) return 1;
long res = 1;
for (int i = 0; i < k; i++) {
res = res * (n - i) / (i + 1);
}
return res;
}
public static int TriangularSum(int[] nums) {
int result = 0;
int n = nums.Length;
for (int i = 0; i < n; i++) {
result = (result + nums[i] * (int)Combination(n - 1, i)) % 10;
}
return result;
}
public static void Main() {
int[] nums = {1, 2, 3, 4, 5};
Console.WriteLine(TriangularSum(nums));
}
}The Python solution utilizes the `comb` function to compute coefficients directly, simplifying how frequently each number in `nums` contributes to the final value, achieving the result efficiently.
Time Complexity: O(n^2) for calculating combinations,
Space Complexity: O(1)
Approach 3: Simulation
We can directly simulate the operations described in the problem. Perform n - 1 rounds of operations on the array nums, updating the array nums according to the rules described in the problem for each round. Finally, return the only remaining element in the array nums.
The time complexity is O(n^2), where n is the length of the array nums. The space complexity is O(1).
function triangularSum(nums: number[]): number {
for (let k = nums.length - 1; k; --k) {
for (let i = 0; i < k; ++i) {
nums[i] = (nums[i] + nums[i + 1]) % 10;
}
}
return nums[0];
}func triangularSum(nums []int) int {
for k := len(nums) - 1; k > 0; k-- {
for i := 0; i < k; i++ {
nums[i] = (nums[i] + nums[i+1]) % 10
}
}
return nums[0]
}impl Solution {
pub fn triangular_sum(mut nums: Vec<i32>) -> i32 {
let mut k = nums.len() as i32 - 1;
while k > 0 {
for i in 0..k as usize {
nums[i] = (nums[i] + nums[i + 1]) % 10;
}
k -= 1;
}
nums[0]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n^2) |
| Combinatorial Formula | Time Complexity: O(n^2) for calculating combinations, |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Simulation | O(n^2) | O(1) | Best for quick implementation or when constraints are small |
| Combinatorial Formula (Pascal's Triangle Insight) | O(n) | O(1) | Preferred for large inputs and when recognizing binomial coefficient patterns |
Frequently asked questions
Is Find Triangular Sum of an Array easy or hard?
The problem is generally rated medium difficulty. The simulation solution is straightforward, but recognizing the Pascal's triangle relationship and deriving the combinatorial formula requires stronger mathematical and algorithmic insight.
Find Triangular Sum of an Array Python/Java solution
Python, Java, C++, C#, and JavaScript implementations typically start with the iterative simulation because it directly follows the problem statement. Optimized versions compute binomial coefficients and accumulate the weighted sum to achieve O(n) performance.
How to solve Find Triangular Sum of an Array in O(n)?
Use the identity that the final element equals the weighted sum of the original array with binomial coefficients from row n-1 of Pascal's triangle. Compute each coefficient iteratively and accumulate nums[i] * C(n-1, i) mod 10. This processes the array once, giving O(n) time.
What is the best approach for Find Triangular Sum of an Array?
The most efficient approach uses a combinatorial formula based on Pascal's triangle. The final triangular sum equals sum(nums[i] * C(n-1, i)) mod 10. This avoids repeated simulation and computes the answer in O(n) time and O(1) space.
Is Find Triangular Sum of an Array asked at Google/Amazon/Meta?
This problem reflects common interview themes such as array simulation and recognizing mathematical patterns like Pascal's triangle. Variations involving triangular reductions or combinatorial transformations have appeared in interviews at large tech companies including Google and Amazon.
What data structure is used in Find Triangular Sum of an Array?
The core data structure is a simple array. The simulation approach repeatedly updates adjacent elements, while the optimized solution treats the array as coefficients in a combinatorial expansion using binomial coefficients.
What is the time complexity of Find Triangular Sum of an Array?
The straightforward simulation takes O(n^2) time because each iteration processes nearly the entire array and the length shrinks by one each round. Using the binomial coefficient observation reduces the complexity to O(n) time with constant extra space.