Complex Array Manipulation Techniques in C++

Introduction

Hello there! Are you ready to solve another engaging problem today? We have a practical task that will enhance your problem-solving skills. It involves critical aspects of programming — dealing with arrays and using techniques such as sorting and the two-pointer method . So, let's jump in!

Task Statement

1

Solution Building: Step 1

Let's embark on our solution-building journey by constructing a sorted array for array B. This array will include pairs of values (val) and their corresponding indices (idx) from array B. Here, val represents the element in B, while idx denotes the index at which val is found in array B. This sorted array will be similar to an associative array, storing 'value-index' pairs. It not only organizes the data for efficient retrieval but also makes it easier for us to traverse the array. Here's the introductory part of our C++ function, including the complete sorted array: C++#include <vector> #include <algorithm> #include <cmath> std::vector<int> find_and_replace(std::vector<int>& A, std::vector<int>& B) { std::vector<std::pair<int, int>> B_sorted; for (int i = 0; i < B.size(); i++) { B_sorted.push_back(std::make_pair(B[i], i)); } std::sort(B_sorted.begin(), B_sorted.end()); In the above code, we generate an array of pairs comprising the values from B and their respective indices using a simple loop. Then, the std::sort function arranges these pairs in ascending order of their values.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Solution Building: Step 4

In this final step, we employ the indices from B_sorted to alter the appropriate elements in array A. Based on the position of the right pointer j, we replace the corresponding element in res with the element in A located at the same index.

C++

#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

std::vector<int> find_and_replace(std::vector<int>& A, std::vector<int>& B) {
    std::vector<std::pair<int, int>> B_sorted;
    for (int i = 0; i < B.size(); i++) {
        B_sorted.push_back(std::make_pair(B[i], i));
    }
    std::sort(B_sorted.begin(), B_sorted.end());

    int j = 0;  // Initialize right pointer
    std::vector<int> res(A.size(), 0);  // Initialize the result array
    
    for (int i = 0; i < B.size(); i++) {
        int target = 2 * B_sorted[i].first;  // The target is twice the current number in the sorted B
        while (j < B.size() - 1 && B_sorted[j+1].first < target) {
            j++;  // Move the right pointer to find a number smaller than or equal to the target
        }
        if (j < B.size() - 1 && std::abs(B_sorted[j+1].first - target) < std::abs(target - B_sorted[j].first)) {
            j++;  // Move the right pointer one more step if the next number is closer to the target
        }
        res[B_sorted[i].second] = A[B_sorted[j].second];  
        // Collect the corresponding element from A at the same index as the closest number in B_sorted
    }

    return res;
}

int main() {
    std::vector<int> A = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110};
    std::vector<int> B = {4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100};
    std::vector<int> result = find_and_replace(A, B);
    for (int elm : result) {
        std::cout << elm << ' ';
    }
    return 0;
}

#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

std::vector<int> find_and_replace(std::vector<int>& A, std::vector<int>& B) {
    std::vector<std::pair<int, int>> B_sorted;
    for (int i = 0; i < B.size(); i++) {
        B_sorted.push_back(std::make_pair(B[i], i));
    }
    std::sort(B_sorted.begin(), B_sorted.end());

    int j = 0;  // Initialize right pointer
    std::vector<int> res(A.size(), 0);  // Initialize the result array
    
    for (int i = 0; i < B.size(); i++) {
        int target = 2 * B_sorted[i].first;  // The target is twice the current number in the sorted B
        while (j < B.size() - 1 && B_sorted[j+1].first < target) {
            j++;  // Move the right pointer to find a number smaller than or equal to the target
        }
        if (j < B.size() - 1 && std::abs(B_sorted[j+1].first - target) < std::abs(target - B_sorted[j].first)) {
            j++;  // Move the right pointer one more step if the next number is closer to the target
        }
        res[B_sorted[i].second] = A[B_sorted[j].second];  
        // Collect the corresponding element from A at the same index as the closest number in B_sorted
    }

    return res;
}

int main() {
    std::vector<int> A = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110};
    std::vector<int> B = {4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100};
    std::vector<int> result = find_and_replace(A, B);
    for (int elm : result) {
        std::cout << elm << ' ';
    }
    return 0;
}

And there you have it! You've successfully crafted a C++ function capable of producing the required output. This C++ function iteratively replaces each element in array A according to the defined logic and returns the modified array.

std::vector<int> find_and_replace(std::vector<int>& A, std::vector<int>& B) { std::vector<std::pair<int, int>> B_sorted; for (int i = 0; i < B.size(); i++) { B_sorted.push_back(std::make_pair(B[i], i)); } std::sort(B_sorted.begin(), B_sorted.end()); int j = 0; // Initialize right pointer std::vector<int> res(A.size(), 0); // Initialize the result array for (int i = 0; i < B.size(); i++) { int target = 2 * B_sorted[i].first; // The target is twice the current number in the sorted B while (j < B.size() - 1 && B_sorted[j+1].first < target) { j++; // Move the right pointer to find a number smaller than or equal to the target } if (j < B.size() - 1 && std::abs(B_sorted[j+1].first - target) < std::abs(target - B_sorted[j].first)) { j++; // Move the right pointer one more step if the next number is closer to the target }

Introduction

Task Statement

Solution Building: Step 1

Join the 1M+ learners on CodeSignal

Solution Building: Step 2

Solution Building: Step 3

Solution Building: Step 4

Complexity Analysis

Lesson Summary