Find the Array Concatenation Value - Solution & Explanation
Problem Statement
You are given a 0-indexed integer array nums.
The concatenation of two numbers is the number formed by concatenating their numerals.
- For example, the concatenation of
15,49is1549.
The concatenation value of nums is initially equal to 0. Perform this operation until nums becomes empty:
- If there exists more than one number in
nums, pick the first element and last element innumsrespectively and add the value of their concatenation to the concatenation value ofnums, then delete the first and last element fromnums. - If one element exists, add its value to the concatenation value of
nums, then delete it.
Return the concatenation value of the nums.
Example 1:
Input: nums = [7,52,2,4] Output: 596 Explanation: Before performing any operation, nums is [7,52,2,4] and concatenation value is 0. - In the first operation: We pick the first element, 7, and the last element, 4. Their concatenation is 74, and we add it to the concatenation value, so it becomes equal to 74. Then we delete them from nums, so nums becomes equal to [52,2]. - In the second operation: We pick the first element, 52, and the last element, 2. Their concatenation is 522, and we add it to the concatenation value, so it becomes equal to 596. Then we delete them from the nums, so nums becomes empty. Since the concatenation value is 596 so the answer is 596.
Example 2:
Input: nums = [5,14,13,8,12] Output: 673 Explanation: Before performing any operation, nums is [5,14,13,8,12] and concatenation value is 0. - In the first operation: We pick the first element, 5, and the last element, 12. Their concatenation is 512, and we add it to the concatenation value, so it becomes equal to 512. Then we delete them from the nums, so nums becomes equal to [14,13,8]. - In the second operation: We pick the first element, 14, and the last element, 8. Their concatenation is 148, and we add it to the concatenation value, so it becomes equal to 660. Then we delete them from the nums, so nums becomes equal to [13]. - In the third operation: nums has only one element, so we pick 13 and add it to the concatenation value, so it becomes equal to 673. Then we delete it from nums, so nums become empty. Since the concatenation value is 673 so the answer is 673.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 104
Approach Overview
Problem Overview: You are given an integer array nums. Repeatedly take the first and last elements, concatenate them into a new number, and add it to a running total. If only one element remains, add it directly. Continue until the array is exhausted and return the final sum.
Approach 1: Two-Pointer Approach (O(n) time, O(1) space)
This method processes the array from both ends using two indices. Start with left = 0 and right = n - 1. On each step, concatenate nums[left] and nums[right] by converting to strings or by multiplying the left value by a power of 10 based on the number of digits in the right value. Add the resulting number to the total, then move both pointers inward. When left == right, add that element directly because it cannot form a pair. This technique scans the array once, so the time complexity is O(n) and the algorithm uses O(1) extra space. The logic is a classic application of two pointers on an array, combined with straightforward simulation of the process described in the problem.
The key insight is that the operation only depends on symmetric positions in the array. Instead of modifying the array or repeatedly removing elements, two pointers allow you to simulate the exact behavior while keeping the implementation simple and efficient. Each iteration handles two elements, so the number of operations scales linearly with the array size.
Approach 2: Stack-Based Approach (O(n) time, O(n) space)
A stack can simulate access to the last element while iterating from the front. Push all elements of the array onto a stack, then iterate from the start of the array. For each element, pop the top of the stack to obtain the corresponding last element. Concatenate the two values and add them to the result. Stop when the iteration index crosses the remaining stack size. If the same element would be used twice (middle element in an odd-length array), add it directly instead of concatenating.
This approach also runs in O(n) time because each element is pushed and popped once. However, it requires O(n) extra space for the stack. The implementation is conceptually simple but less space-efficient than the two-pointer method. It can still be useful when practicing stack operations or when the input structure naturally arrives in a streaming order where reverse access is needed.
Recommended for interviews: The two-pointer approach is the expected solution. It achieves O(n) time with O(1) space and directly models the first-and-last pairing described in the problem. Showing the stack version demonstrates understanding of alternative data structures, but the constant-space two-pointer solution highlights stronger algorithmic judgment.
Approach 1: Two-pointer Approach
This approach uses two pointers to track the first and last elements of the array. By incrementing the start pointer and decrementing the end pointer, we efficiently process the array from both ends, concatenating values along the way.
This C program uses sprintf to format and concatenate numbers as strings, converting the result back to an integer using atoi before adding it to the sum.
Complexity
Time Complexity: O(n). Space Complexity: O(1), aside from the negligible buffer space.
Approach 2: Stack-Based Approach
Using a stack to keep track of the numbers effectively simplifies the task of processing from both ends. By pushing numbers onto a stack and then popping them, we manage concatenations seamlessly.
This C code uses an explicit stack to simulate removal and processing of array elements, maintaining a clean traversal of the list.
Complexity
Time Complexity: O(n^2) due to shifting operations on the stack. Space Complexity: O(n) for the stack.
Approach 3: Simulation
Starting from both ends of the array, we take out one element at a time, concatenate it with another element, and then add the concatenated result to the answer. We repeat this process until the array is empty.
The time complexity is O(n times log M), and the space complexity is O(log M). Here, n and M are the length of the array and the maximum value in the array, respectively.
Approach 4: Default Approach
Code
Rust
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-pointer Approach | Time Complexity: O(n). Space Complexity: O(1), aside from the negligible buffer space. |
| Stack-Based Approach | Time Complexity: O(n^2) due to shifting operations on the stack. Space Complexity: O(n) for the stack. |
| Simulation | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Approach | O(n) | O(1) | Best general solution. Processes both ends of the array in one pass with constant extra memory. |
| Stack-Based Approach | O(n) | O(n) | Useful when practicing stack operations or when reverse access is easier through a stack. |
Video Solution
Leetcode | 2562. Find the Array Concatenation Value | Easy | Java Solution • Developer Docs • 771 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Array Concatenation Value easy or hard?
Find the Array Concatenation Value Python/Java solution
How to solve Find the Array Concatenation Value in O(n)?
What is the best approach for Find the Array Concatenation Value?
Is Find the Array Concatenation Value asked at Google/Amazon/Meta?
What data structure is used in Find the Array Concatenation Value?
What is the time complexity of Find the Array Concatenation Value?
Ready to solve this problem?
Practice Find the Array Concatenation Value with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor