# Find the Array Concatenation Value
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-array-concatenation-value)
Canonical: https://scaleengineer.com/dsa/problems/find-the-array-concatenation-value
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## Problem
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`, `49` is `1549`.

The **concatenation value** of `nums` is initially equal to `0`. Perform this operation until `nums` becomes empty:

* If `nums` has a size greater than one, add the value of the concatenation of the first and the last element to the **concatenation value** of `nums`, and remove those two elements from `nums`. For example, if the `nums` was `[1, 2, 4, 5, 6]`, add 16 to the `concatenation value`.
* If only one element exists in `nums`, add its value to the **concatenation value** of `nums`, 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 <= 1000`
* `1 <= nums[i] <= 104`

# Approaches
## Simulation using ArrayList
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.
**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`.
**Pros:** Simple to understand and implement as it directly follows the problem description.
**Cons:** Inefficient due to the `remove(0)` operation on `ArrayList`. 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`.
### Explanation
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 to `concatenationValue`. Afterwards, we remove the first element using `list.remove(0)` and the last element using `list.remove(list.size() - 1)`.
- If the size is exactly one, we simply add the value of this single element to `concatenationValue` and then remove it.
The process repeats until the list is exhausted. Finally, the total `concatenationValue` is returned.
The main drawback of this method is the performance of `list.remove(0)` on an `ArrayList`, which is an O(n) operation as it requires shifting all subsequent elements.
```java
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;
    }
}
```
### Algorithm
- Convert the input array `nums` into an `ArrayList`.
- Initialize `concatenationValue = 0`.
- While the list is not empty:
    - If `list.size() > 1`:
        - Get `first = list.get(0)` and `last = list.get(list.size() - 1)`.
        - Concatenate `first` and `last` (e.g., via string conversion) to get `concatenatedNum`.
        - Add `concatenatedNum` to `concatenationValue`.
        - Remove the first and last elements from the list.
    - Else (if `list.size() == 1`):
        - Add `list.get(0)` to `concatenationValue`.
        - Remove the element from the list.
- Return `concatenationValue`.

## Simulation using a Deque
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`.
**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.
**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.
### Explanation
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()` and `deque.pollLast()` to retrieve and remove the elements from both ends in O(1) time. We then concatenate them and add the result to `concatenationValue`.
- If only one element remains, we retrieve it with `deque.pollFirst()`, add its value to `concatenationValue`, and the deque becomes empty.
This process continues until the deque is empty, and we return the final `concatenationValue`. This method is significantly faster than the `ArrayList` approach.
```java
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;
    }
}
```
### Algorithm
- Create a `Deque` (e.g., `ArrayDeque` or `LinkedList`) and add all elements from `nums` to it.
- Initialize `concatenationValue = 0`.
- While the deque is not empty:
    - If `deque.size() > 1`:
        - Get `first = deque.pollFirst()` and `last = deque.pollLast()`.
        - Concatenate `first` and `last` to get `concatenatedNum`.
        - Add `concatenatedNum` to `concatenationValue`.
    - Else (if `deque.size() == 1`):
        - Add `deque.pollFirst()` to `concatenationValue`.
- Return `concatenationValue`.

## Two Pointers
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.
**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.
**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.
### Explanation
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 take `nums[left]` and `nums[right]`, concatenate them, and add the result to `concatenationValue`. Then, we move the pointers closer by incrementing `left` and decrementing `right`.
- 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]`, to `concatenationValue`. The loop will terminate after this iteration as `left` will become greater than `right`.
The concatenation can be done either by converting numbers to strings or using a mathematical approach. For example, to concatenate `a` and `b`, we can calculate `a * 10^d + b`, where `d` is the number of digits in `b`.
This approach avoids any extra space and is very efficient.
```java
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;
    }
}
```
### Algorithm
- Initialize `concatenationValue = 0`, `left = 0`, `right = nums.length - 1`.
- While `left <= right`:
    - If `left < right`:
        - Get `first = nums[left]` and `last = nums[right]`.
        - Concatenate `first` and `last` to get `concatenatedNum`.
        - Add `concatenatedNum` to `concatenationValue`.
        - Increment `left` and decrement `right`.
    - Else (if `left == right`):
        - Add `nums[left]` to `concatenationValue`.
        - Increment `left` (or `break`).
- Return `concatenationValue`.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```