algoadvance

Leetcode 2562. Find the Array Concatenation Value

Problem Statement

Given a 0-indexed integer array nums, the concatenation value of nums is initially empty. Initially, the length of nums is n.

Perform the following steps until nums becomes empty:

  1. If there is only one element in nums, move the final element to the concatenation value.
  2. Otherwise, choose a pair of elements from nums, the first being the leftmost element and the second being the rightmost element.
  3. Remove both elements from nums and add their concatenation to the concatenation value.

The concatenation of two integers means the concatenated form of their string representations. For example, if the left number is 12 and the right number is 34, the concatenation is “1234”.

Return the concatenation value as an integer.

Clarifying Questions

  1. Input size: What is the maximum possible size of the nums array?
  2. Input values: Are the elements in nums always positive integers?
  3. Output specifics: The final output should be an integer formed by concatenating pairs.

Code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    long long findTheArrayConcVal(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int left = 0;
        int right = nums.size() - 1;
        string result = "";

        while (left <= right) {
            if (left == right) {
                result += to_string(nums[left]);
            } else {
                result += to_string(nums[left]) + to_string(nums[right]);
            }
            left++;
            right--;
        }
        return stoll(result);
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3, 4, 5};
    cout << sol.findTheArrayConcVal(nums) << endl;

    return 0;
}

Strategy

  1. Initialization: Start with two pointers, left at the beginning and right at the end of the array.
  2. Loop until pointers cross:
    • If there is only one element left (i.e., left equals right), append this single element’s string representation to the result.
    • Otherwise, concatenate the string representation of the leftmost and rightmost elements and append them to the result string.
    • Move the left pointer to the right and the right pointer to the left to process the next pair of elements.
  3. Return the result: Convert the final concatenated string to a number using stoll().

Time Complexity

This algorithm efficiently concatenates pairs of integers from the array by leveraging string operations and handles edge cases where the array has an odd length naturally.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI