Get Full Names II in C++ (Time Complexity: O(n))

Given an array of strings names that contain first and last names adjacent to each other, return an array containing the full names (separated by one space)

Example:

Input:  names = ["John", "Doe", "Andy", "Smith", "Mary", "Johnson"]

Output:  ["John Doe", "Andy Smith", "Mary Johnson"]

Understanding the Problem

The core challenge of this problem is to pair adjacent elements in the input array to form full names. Each pair of elements represents a first name followed by a last name. The significance of this problem lies in its simplicity and its common application in data processing tasks where names are often split and need to be combined for display or further processing.

Potential pitfalls include not correctly pairing the names or handling arrays with an odd number of elements, which would be an invalid input based on the problem constraints.

Approach

To solve this problem, we can iterate through the input array in steps of two, combining each pair of elements into a single string separated by a space. This approach ensures that we correctly pair each first name with its corresponding last name.

Let's break down the approach:

Initialize an empty result array to store the full names.
Iterate through the input array in steps of two.
For each pair of elements, concatenate them with a space in between and add the resulting string to the result array.
Return the result array.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Initialize an empty vector fullNames to store the full names.
Loop through the input array names with a step of 2.
In each iteration, concatenate the current element and the next element with a space in between.
Push the concatenated string into the fullNames vector.
After the loop, return the fullNames vector.

Code Implementation


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

std::vector<std::string> getFullNames(const std::vector<std::string>& names) {
    std::vector<std::string> fullNames;
    for (size_t i = 0; i < names.size(); i += 2) {
        // Concatenate the first name and last name with a space
        std::string fullName = names[i] + " " + names[i + 1];
        fullNames.push_back(fullName);
    }
    return fullNames;
}

int main() {
    std::vector<std::string> names = {"John", "Doe", "Andy", "Smith", "Mary", "Johnson"};
    std::vector<std::string> result = getFullNames(names);

    // Print the result
    for (const std::string& name : result) {
        std::cout << name << std::endl;
    }

    return 0;
}

Complexity Analysis

The time complexity of this approach is O(n), where n is the number of elements in the input array. This is because we iterate through the array once, performing a constant amount of work for each pair of elements.

The space complexity is also O(n) because we store the full names in a new vector, which in the worst case will have the same number of elements as the input array.

Edge Cases

Potential edge cases include:

An empty input array: The function should return an empty array.
An array with an odd number of elements: This is an invalid input based on the problem constraints, so we assume the input will always have an even number of elements.

Testing

To test the solution comprehensively, consider the following test cases:

Standard case with multiple pairs of names.
Empty input array.
Single pair of names.

Example test cases:

Input: names = ["John", "Doe", "Andy", "Smith", "Mary", "Johnson"]
Output: ["John Doe", "Andy Smith", "Mary Johnson"]

Input: names = []
Output: []

Input: names = ["Alice", "Wonderland"]
Output: ["Alice Wonderland"]

Thinking and Problem-Solving Tips

When approaching such problems, it's important to:

Carefully read the problem statement and understand the input and output requirements.
Break down the problem into smaller, manageable steps.
Consider edge cases and how to handle them.
Write clean, readable code with comments to explain your thought process.

To improve problem-solving skills, practice solving similar problems and study different algorithms and data structures.

Conclusion

In this blog post, we discussed how to solve the problem of combining adjacent first and last names into full names using a simple and efficient approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

Additional Resources

For further reading and practice, consider the following resources: