Sponsored
Sponsored
The two-pointer technique involves using two pointers, one starting at the beginning of the array and the other at the end. Swap the characters at the two pointers and then move the pointers inwards towards each other until they meet or cross. This method efficiently reverses the array in-place with O(1) extra space.
Time Complexity: O(n) where n is the number of characters in the string.
Space Complexity: O(1) as it uses a fixed amount of extra space.
1#include <stdio.h>
2
3void reverseString(char* s, int sSize) {
4 int left = 0, right = sSize - 1;
5 while (left < right) {
6 char temp = s[left];
7 s[left] = s[right];
8 s[right] = temp;
9 left++;
10 right--;
11 }
12}
13The C solution uses a while loop with two pointers, left and right, to swap the characters until the entire string is reversed. The process continues until the left pointer is not less than the right pointer.
This approach uses recursion to swap characters at symmetric positions while visually simplifying the problem. The base case is when the left index is not less than the right index.
Time Complexity: O(n).
Space Complexity: O(n) due to call stack depth.
1#include <vector>
2using namespace std;
void reverseUtil(vector<char>& s, int left, int right) {
if (left >= right) return;
swap(s[left], s[right]);
reverseUtil(s, left + 1, right - 1);
}
void reverseString(vector<char>& s) {
reverseUtil(s, 0, s.size() - 1);
}
C++ version also recursively swaps characters, utilizing the standard library swap function in a similar fashion as iterative but recursively.