Find the Array Concatenation Value
EasyPrompt
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
numshas a size greater than one, add the value of the concatenation of the first and the last element to the concatenation value ofnums, and remove those two elements fromnums. For example, if thenumswas[1, 2, 4, 5, 6], add 16 to theconcatenation value. - If only one element exists in
nums, add its value to the concatenation value ofnums, then remove it.
Return the concatenation value of 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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We convert the input array into an ArrayList to facilitate the removal of elements. In each step, we take the first and last elements, calculate their concatenation value, add it to a running total, and then remove them from the list. This continues until the list is empty.
Algorithm
- Convert the input array
numsinto anArrayList. - Initialize
concatenationValue = 0. - While the list is not empty:
- If
list.size() > 1:- Get
first = list.get(0)andlast = list.get(list.size() - 1). - Concatenate
firstandlast(e.g., via string conversion) to getconcatenatedNum. - Add
concatenatedNumtoconcatenationValue. - Remove the first and last elements from the list.
- Get
- Else (if
list.size() == 1):- Add
list.get(0)toconcatenationValue. - Remove the element from the list.
- Add
- If
- Return
concatenationValue.
Walkthrough
We start by converting the input integer array nums into a java.util.ArrayList. This allows for dynamic resizing and element removal.
A long variable, concatenationValue, is initialized to 0 to store the cumulative result.
We enter a loop that continues as long as the list is not empty.
Inside the loop, we check the size of the list.
- If the size is greater than one, we retrieve the first and last elements. To concatenate them, we convert them to strings, join the strings, and then parse the result back into a
long. This value is added toconcatenationValue. Afterwards, we remove the first element usinglist.remove(0)and the last element usinglist.remove(list.size() - 1). - If the size is exactly one, we simply add the value of this single element to
concatenationValueand then remove it. The process repeats until the list is exhausted. Finally, the totalconcatenationValueis returned. The main drawback of this method is the performance oflist.remove(0)on anArrayList, which is an O(n) operation as it requires shifting all subsequent elements.
import java.util.ArrayList;import java.util.List; class Solution { public long findTheArrayConcVal(int[] nums) { List<Integer> numList = new ArrayList<>(); for (int num : nums) { numList.add(num); } long concatenationValue = 0; while (!numList.isEmpty()) { if (numList.size() > 1) { int first = numList.get(0); int last = numList.get(numList.size() - 1); String s = Integer.toString(first) + Integer.toString(last); concatenationValue += Long.parseLong(s); numList.remove(0); numList.remove(numList.size() - 1); } else { concatenationValue += numList.get(0); numList.remove(0); } } return concatenationValue; }}Complexity
Time
O(N^2), where N is the number of elements in `nums`. The conversion to a list takes O(N). The `while` loop runs N/2 times. Inside the loop, `remove(0)` takes O(k) time where k is the current list size. The sum of these removal times is `(N-1) + (N-3) + ...`, which is O(N^2).
Space
O(N) to store the `ArrayList`.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem description.
Cons
Inefficient due to the
remove(0)operation onArrayList. Removing the first element takes time proportional to the current size of the list, leading to a quadratic time complexity overall.Requires extra space to store the
ArrayList.
This approach improves upon the previous one by using a more suitable data structure. A Deque (Double-Ended Queue), implemented using a LinkedList or ArrayDeque, provides efficient O(1) time complexity for adding and removing elements from both ends. This avoids the costly O(n) removal from the front of an ArrayList.
Algorithm
- Create a
Deque(e.g.,ArrayDequeorLinkedList) and add all elements fromnumsto it. - Initialize
concatenationValue = 0. - While the deque is not empty:
- If
deque.size() > 1:- Get
first = deque.pollFirst()andlast = deque.pollLast(). - Concatenate
firstandlastto getconcatenatedNum. - Add
concatenatedNumtoconcatenationValue.
- Get
- Else (if
deque.size() == 1):- Add
deque.pollFirst()toconcatenationValue.
- Add
- If
- Return
concatenationValue.
Walkthrough
We first populate a Deque, such as a java.util.ArrayDeque, with the elements from the input nums array.
A long variable, concatenationValue, is initialized to 0.
We iterate as long as the deque contains elements.
In each iteration, we check the deque's size.
- If there are more than one element, we use
deque.pollFirst()anddeque.pollLast()to retrieve and remove the elements from both ends in O(1) time. We then concatenate them and add the result toconcatenationValue. - If only one element remains, we retrieve it with
deque.pollFirst(), add its value toconcatenationValue, and the deque becomes empty. This process continues until the deque is empty, and we return the finalconcatenationValue. This method is significantly faster than theArrayListapproach.
import java.util.ArrayDeque;import java.util.Deque; class Solution { public long findTheArrayConcVal(int[] nums) { Deque<Integer> deque = new ArrayDeque<>(); for (int num : nums) { deque.add(num); } long concatenationValue = 0; while (!deque.isEmpty()) { if (deque.size() > 1) { int first = deque.pollFirst(); int last = deque.pollLast(); String s = Integer.toString(first) + Integer.toString(last); concatenationValue += Long.parseLong(s); } else { concatenationValue += deque.pollFirst(); } } return concatenationValue; }}Complexity
Time
O(N), where N is the number of elements in `nums`. Populating the deque takes O(N). The loop runs N/2 times, and each operation inside (`pollFirst`, `pollLast`) is O(1). String conversion and parsing depend on the number of digits, which is small and constant, so we can consider it O(1) per operation.
Space
O(N) to store the elements in the deque.
Trade-offs
Pros
Efficient time complexity due to O(1) operations for accessing and removing elements from both ends of the deque.
Still conceptually simple and follows the problem logic closely.
Cons
Requires O(N) extra space to create the deque, which can be avoided.
This is the most optimal approach. Instead of using an auxiliary data structure, we can work directly on the input array nums using two pointers. One pointer (left) starts at the beginning of the array, and the other (right) starts at the end. The pointers move towards each other, processing pairs of elements until they meet or cross.
Algorithm
- Initialize
concatenationValue = 0,left = 0,right = nums.length - 1. - While
left <= right:- If
left < right:- Get
first = nums[left]andlast = nums[right]. - Concatenate
firstandlastto getconcatenatedNum. - Add
concatenatedNumtoconcatenationValue. - Increment
leftand decrementright.
- Get
- Else (if
left == right):- Add
nums[left]toconcatenationValue. - Increment
left(orbreak).
- Add
- If
- Return
concatenationValue.
Walkthrough
We initialize a long variable concatenationValue to 0.
We use two integer pointers, left starting at index 0 and right starting at the last index nums.length - 1.
We loop as long as left is less than or equal to right.
Inside the loop:
- If
left < right, it means we have a pair of elements to process. We takenums[left]andnums[right], concatenate them, and add the result toconcatenationValue. Then, we move the pointers closer by incrementingleftand decrementingright. - If
left == right, it means we have a single element left in the middle of the array (for arrays with an odd number of elements). We add this element's value,nums[left], toconcatenationValue. The loop will terminate after this iteration asleftwill become greater thanright. The concatenation can be done either by converting numbers to strings or using a mathematical approach. For example, to concatenateaandb, we can calculatea * 10^d + b, wheredis the number of digits inb. This approach avoids any extra space and is very efficient.
class Solution { public long findTheArrayConcVal(int[] nums) { long concatenationValue = 0; int left = 0; int right = nums.length - 1; while (left <= right) { if (left < right) { int first = nums[left]; int last = nums[right]; // Using string conversion for simplicity String s = Integer.toString(first) + Integer.toString(last); concatenationValue += Long.parseLong(s); left++; right--; } else { // left == right concatenationValue += nums[left]; left++; // or break } } return concatenationValue; }}Complexity
Time
O(N), where N is the number of elements in `nums`. The `while` loop iterates through the array once with two pointers, effectively processing each element once.
Space
O(1), as we only use a few variables to store the pointers and the result, regardless of the input size.
Trade-offs
Pros
Optimal space complexity of O(1) as it modifies no data structures and uses only a few variables.
Optimal time complexity of O(N) as it iterates through the array only once.
In-place processing of the input array.
Cons
None, this is the most efficient and recommended approach.
Solutions
Solution
class Solution { public long findTheArrayConcVal ( int [] nums ) { long ans = 0 ; int i = 0 , j = nums . length - 1 ; for (; i < j ; ++ i , -- j ) { ans += Integer . parseInt ( nums [ i ] + "" + nums [ j ]); } if ( i == j ) { ans += nums [ i ]; } return ans ; } }class Solution {public: long long findTheArrayConcVal(vector<int> &nums) { long long ans = 0; int i = 0, j = nums.size() - 1; for (; i < j; ++i, --j) { ans += stoi(to_string(nums[i]) + to_string(nums[j])); } if (i == j) { ans += nums[i]; } return ans; }};class Solution: def findTheArrayConcVal(self, nums: List[int]) -> int: ans = 0 i, j = 0, len(nums) - 1 while i < j: ans += int(str(nums[i]) + str(nums[j])) i, j = i + 1, j - 1 if i == j: ans += nums[i] return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.