2562. Find the Array Concatenation Value

EasyArrayTwo PointersSimulation
Leetcode Link

Problem Description

This LeetCode problem involves manipulating an array of integers to calculate what is referred to as a "concatenation value". Here's what you need to know:

  • You have an array of integers called nums, with each element having a 0-based index.
  • The term "concatenation" of two numbers here refers to creating a new number by joining the digit sequences of both numbers end to end.
    • For example, concatenating 15 and 49 yields 1549.
  • Initially, the concatenation value is 0.
  • To find the final concatenation value, you go through the following steps:
    1. If nums contains more than one number, take the first and last elements.
    2. Concatenate those two elements and add their concatenation's numerical value to the concatenation value of nums.
    3. Remove the first and last elements from nums.
    4. If only one number exists in nums, add its value to the concatenation value and remove it.
  • This process repeats until nums is empty.
  • Your goal is to return the final concatenation value after all elements are combined and removed according to the steps above.

Intuition

To approach the solution to this problem, you start by understanding that you'll be reducing the array from both ends until there are no more elements left to process.

Here's how you arrive at the solution step-by-step:

  • Recognize that array elements should be considered from both ends.
  • At each step where there are at least two elements, you consider the first and last element for the operation.
    • You convert each number to a string, concatenate those strings, then convert the resulting string back to an integer.
    • Add this integer to the running total of the concatenation value.
  • If there's only one element left in the process, simply add its value to the total.
  • This process is repeated, updating two pointers (i and j) that represent the current first and last elements in the array.
  • When the pointers meet or cross, you've processed all elements.
  • The final concatenation value can be returned after considering all elements in the required manner.

Learn more about Two Pointers 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 the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The implementation of the solution uses a straightforward simulation algorithm with two pointers. Let's go through the specifics:

  • We start by initializing an accumulator for the answer, ans, to start summing up the concatenation values.

  • Two pointers, i and j, are used to traverse the nums array from both ends toward the center.

    • i is initialized to 0 as the start of the array.
    • j is initialized to the last index of the array, which is len(nums) - 1.

  • We enter a while loop that continues as long as i < j indicating there are at least two elements in the current subrange.

    • Inside the loop, we concatenate the numerical strings of nums[i] and nums[j], by doing str(nums[i]) + str(nums[j]), and then convert this string back to an integer using int().
    • The resultant integer is added to the ans accumulator.

  • After concatenating and adding to ans, we advance i forward by one (i += 1) and move j backward by one (j -= 1) to move towards the center of the array.

  • If we exit the loop and find that i == j, it means there is one remaining element in the array which wasn't processed by the while loop because it has no pair element.

    • In that case, we simply add the value of this last remaining element (nums[i]) to ans.

  • The solution approach is completed by returning the ans variable which contains the final concatenation value after the simulation.

This problem does not require any complex data structures or algorithms, as it simply utilizes basic array manipulation and integer operations. The core pattern here is the two-pointer technique that allows us to efficiently process elements from both ends of the array.

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

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

Example Walkthrough

Let's consider a small example to illustrate the solution approach with the nums array nums = [5,6,2,8].

  1. Initialize ans = 0 to keep track of the concatenation value.
  2. Initialize two pointers: i = 0 for the start of the array and j = len(nums) - 1 = 3 for the end of the array.

Now we start the while loop:

  1. First iteration:

    • Since i < j, concatenate the first and last elements: nums[i] is 5 and nums[j] is 8.
    • Their concatenation as strings is '5' + '8' which is '58'. Convert this back to an integer to get 58.
    • Add this to ans: ans = ans + 58, which makes ans = 58.
    • Now, increment i so i = 1 and decrement j so j = 2.

  2. Second iteration:

    • The condition i < j still holds true.
    • Concatenate nums[i] which is 6 and nums[j] which is 2 to get '62'.
    • As an integer, it is 62. Update ans = 58 + 62, making ans = 120.
    • Move i to i = 2 and j to j = 1.

  3. Now, i >= j, and the while loop condition is not met. However, we don't have an element that's unpaired. If there were an unpaired element, we would add its value directly to ans.

  4. Since all elements have been processed, the final concatenation value is the current value of ans, which is 120. We return ans.

Therefore, the final concatenation value for the input array [5,6,2,8] using the solution approach provided would be 120.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findTheArrayConcVal(self, nums: List[int]) -> int:
5        # Initialize the answer to 0
6        answer = 0
7      
8        # Set pointers for the start and end of the array
9        left, right = 0, len(nums) - 1
10      
11        # Loop until the pointers meet or cross
12        while left < right:
13            # Concatenate the numbers at the pointers, convert to int and add to the answer
14            answer += int(str(nums[left]) + str(nums[right]))
15          
16            # Move the pointers towards the center
17            left, right = left + 1, right - 1
18      
19        # If there is a middle element (odd number of elements), add it to the answer
20        if left == right:
21            answer += nums[left]
22      
23        # Return the final answer
24        return answer
25
1class Solution {
2
3    /**
4     * Calculates the "array conc val" by concatenating pairs of elements
5     * from the beginning and end of the array moving towards the center.
6     * If there's a middle element (odd number of elements), it adds it as is.
7     * 
8     * @param nums An array of integers.
9     * @return The calculated "array conc val".
10     */
11    public long findTheArrayConcVal(int[] nums) {
12        long result = 0; // Initialize the result variable.
13
14        int leftIndex = 0; // Start at the beginning of the array.
15        int rightIndex = nums.length - 1; // Start at the end of the array.
16
17        // Loop through the array from both ends until indices meet or cross.
18        while (leftIndex < rightIndex) {
19            // Concatenate the elements at current indices as strings,
20            // convert the result to integer, and add it to the result.
21            result += Long.parseLong(nums[leftIndex] + "" + nums[rightIndex]);
22          
23            // Move the left index forward and the right index backward.
24            leftIndex++;
25            rightIndex--;
26        }
27      
28        // Check if there's a middle element left (in case of odd number of elements).
29        if (leftIndex == rightIndex) {
30            // Add the middle element directly to the result.
31            result += nums[leftIndex];
32        }
33
34        return result; // Return the computed "array conc val".
35    }
36}
37
1class Solution {
2public:
3    // Function to find the array concatenated value
4    long long findTheArrayConcVal(vector<int>& nums) {
5        long long concatenatedSum = 0; // Initialize sum of concatenated values
6        int left = 0; // Starting index from the beginning of the array
7        int right = nums.size() - 1; // Starting index from the end of the array
8
9        // Loop through the array from both ends until the pointers meet or cross
10        while (left < right) {
11            // Concatenate the values at the current indices, convert to number, and add to sum
12            concatenatedSum += stoll(to_string(nums[left]) + to_string(nums[right]));
13          
14            // Move the left pointer forward and the right pointer backward
15            ++left;
16            --right;
17        }
18
19        // If there is a middle element (odd number of elements), add it to the sum
20        if (left == right) {
21            concatenatedSum += nums[left];
22        }
23
24        // Return the final concatenated sum
25        return concatenatedSum;
26    }
27};
28
1// This function finds a value based on the concatenation of array elements.
2// Pairs the first and last elements moving inwards and adds their concatenation.
3// If there is an unpaired middle element, it is added directly to the result.
4function findTheArrayConcVal(nums: number[]): number {
5    // Get the length of the array
6    const arrayLength = nums.length;
7    // Initialize the answer to zero
8    let answer = 0;
9    // Initialize the front index
10    let frontIndex = 0;
11    // Initialize the back index
12    let backIndex = arrayLength - 1;
13  
14    // Loop until frontIndex is less than backIndex
15    while (frontIndex < backIndex) {
16        // Concatenate the elements by converting them to strings, adding them, and then converting back to a number
17        answer += Number(`${nums[frontIndex]}${nums[backIndex]}`);
18        // Increment the front index
19        frontIndex++;
20        // Decrement the back index
21        backIndex--;
22    }
23  
24    // If there is a middle element, add it to the answer
25    if (frontIndex === backIndex) {
26        answer += nums[frontIndex];
27    }
28  
29    // Return the calculated answer
30    return answer;
31}
32
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a min heap?

Time and Space Complexity

The provided Python code calculates a special value based on the input nums list. Let's analyze the time and space complexity of this code.

Time Complexity

The time complexity of the algorithm is determined by the while loop, which runs as long as i < j. Since the indices i and j move towards each other with each iteration, the loop executes approximately n/2 times, where n is the total number of elements in nums. Inside this loop, the algorithm concatenates the string representations of numbers at indices i and j, which takes O(\log M) time, where M is the maximum value in the array (since the number of digits of a number x is proportional to \log x).

Thus, the time complexity is O(n/2 × log M), which simplifies to O(n × log M).

Space Complexity

The space complexity of the algorithm is determined by the extra space needed to store the intermediate string representations created during the concatenation operation. The longest possible string is the concatenation of the two largest numbers in nums. Thus, the space complexity is proportional to the length of this string, which is O(2 × \log M). This simplifies to O(\log M) since constant factors are dropped in Big O notation.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

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

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

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 👨‍🏫