TCS Prime Arrays & Strings DSA Questions with
Brute Force & Optimized C++ Solutions
1. Reverse an Array Without Using Extra Space
Brute Force Approach:
// Brute Force
vector<int> temp = arr;
for(int i=0;i<[Link]();i++) {
arr[i] = temp[[Link]()-1-i];
}
Time Complexity: O(n)
Space Complexity: O(n)
Most Optimized Approach:
// Optimized Two Pointer Approach
int start = 0;
int end = [Link]()-1;
while(start < end) {
swap(arr[start], arr[end]);
start++;
end--;
}
Time Complexity: O(n)
Space Complexity: O(1)
2. Find the Second Largest Element
Brute Force Approach:
// Brute Force
sort([Link](), [Link]());
cout << arr[[Link]()-2];
Time Complexity: O(n log n)
Space Complexity: O(1)
Most Optimized Approach:
// Optimized
int largest = INT_MIN;
int secondLargest = INT_MIN;
for(int x : arr) {
if(x > largest) {
secondLargest = largest;
largest = x;
}
else if(x > secondLargest && x != largest) {
secondLargest = x;
}
}
Time Complexity: O(n)
Space Complexity: O(1)
3. Remove Duplicates from Array
Brute Force Approach:
// Brute Force
set<int> s;
for(int x : arr) {
[Link](x);
}
Time Complexity: O(n log n)
Space Complexity: O(n)
Most Optimized Approach:
// Optimized (Sorted Array)
int i = 0;
for(int j = 1; j < [Link](); j++) {
if(arr[i] != arr[j]) {
i++;
arr[i] = arr[j];
}
}
Time Complexity: O(n)
Space Complexity: O(1)
4. Move All Zeros to End
Brute Force Approach:
// Brute Force
vector<int> temp;
for(int x : arr) {
if(x != 0)
temp.push_back(x);
}
while([Link]() < [Link]()) {
temp.push_back(0);
}
Time Complexity: O(n)
Space Complexity: O(n)
Most Optimized Approach:
// Optimized Two Pointer
int j = 0;
for(int i=0;i<[Link]();i++) {
if(arr[i] != 0) {
swap(arr[i], arr[j]);
j++;
}
}
Time Complexity: O(n)
Space Complexity: O(1)
5. Check if Two Strings are Anagrams
Brute Force Approach:
// Brute Force
sort([Link](), [Link]());
sort([Link](), [Link]());
if(s1 == s2)
cout << "Anagram";
Time Complexity: O(n log n)
Space Complexity: O(1)
Most Optimized Approach:
// Optimized Frequency Count
vector<int> freq(26,0);
for(char ch : s1)
freq[ch-'a']++;
for(char ch : s2)
freq[ch-'a']--;
bool flag = true;
for(int x : freq) {
if(x != 0)
flag = false;
}
Time Complexity: O(n)
Space Complexity: O(1)
6. Find Missing Number in Array
Brute Force Approach:
// Brute Force
for(int i=1;i<=n;i++) {
bool found = false;
for(int j=0;j<[Link]();j++) {
if(arr[j] == i) {
found = true;
}
}
if(!found)
cout << i;
}
Time Complexity: O(n²)
Space Complexity: O(1)
Most Optimized Approach:
// Optimized Sum Formula
int total = n*(n+1)/2;
int sum = 0;
for(int x : arr)
sum += x;
cout << total - sum;
Time Complexity: O(n)
Space Complexity: O(1)
7. Kadane's Algorithm
Brute Force Approach:
// Brute Force
int maxi = INT_MIN;
for(int i=0;i<n;i++) {
int sum = 0;
for(int j=i;j<n;j++) {
sum += arr[j];
maxi = max(maxi, sum);
}
}
Time Complexity: O(n²)
Space Complexity: O(1)
Most Optimized Approach:
// Optimized Kadane's Algorithm
int sum = 0;
int maxi = INT_MIN;
for(int x : arr) {
sum += x;
maxi = max(maxi, sum);
if(sum < 0)
sum = 0;
}
Time Complexity: O(n)
Space Complexity: O(1)
8. Rotate Array by K Positions
Brute Force Approach:
// Brute Force
for(int r=0;r<k;r++) {
int last = arr[n-1];
for(int i=n-1;i>0;i--) {
arr[i] = arr[i-1];
}
arr[0] = last;
}
Time Complexity: O(n*k)
Space Complexity: O(1)
Most Optimized Approach:
// Optimized Reverse Technique
reverse([Link](), [Link]());
reverse([Link](), [Link]()+k);
reverse([Link]()+k, [Link]());
Time Complexity: O(n)
Space Complexity: O(1)
9. Longest Substring Without Repeating Characters
Brute Force Approach:
// Brute Force
int maxi = 0;
for(int i=0;i<[Link]();i++) {
set<char> st;
for(int j=i;j<[Link]();j++) {
if([Link](s[j]))
break;
[Link](s[j]);
maxi = max(maxi, j-i+1);
}
}
Time Complexity: O(n²)
Space Complexity: O(n)
Most Optimized Approach:
// Optimized Sliding Window
unordered_map<char,int> mp;
int left = 0;
int maxi = 0;
for(int right=0;right<[Link]();right++) {
if([Link](s[right]) != [Link]()) {
left = max(left, mp[s[right]] + 1);
}
mp[s[right]] = right;
maxi = max(maxi, right-left+1);
}
Time Complexity: O(n)
Space Complexity: O(n)
10. Merge Two Sorted Arrays
Brute Force Approach:
// Brute Force
vector<int> ans;
int i=0,j=0;
while(i<n1 && j<n2) {
if(arr1[i] < arr2[j])
ans.push_back(arr1[i++]);
else
ans.push_back(arr2[j++]);
}
Time Complexity: O(n+m)
Space Complexity: O(n+m)
Most Optimized Approach:
// Optimized Gap Method
int gap = ceil((n+m)/2.0);
while(gap > 0) {
int left = 0;
int right = left + gap;
while(right < n+m) {
// compare and swap logic
left++;
right++;
}
if(gap == 1)
break;
gap = ceil(gap/2.0);
}
Time Complexity: O((n+m) log(n+m))
Space Complexity: O(1)