Arrays & Strings

Problem 
Reverse an array in-place i.e you cannot use any additional array or in other words, space complexity of the solution should be O(1)

Solution 
1) Use two variables (a,b) initialized with the first (0) and last index (n-1) respectively of the array of ‘n’ elements.
2) Swap the values at arr(a) and arr(b).
3) Increment a and decrement b.
4) Repeat step 2 till a and b intersects.

#include<iostream>
using namespace std;

// swap elements of two indexes in the array
void swap(int arr[], int pos1, int pos2) {
   int temp = arr[pos1];
   arr[pos1] = arr[pos2];
   arr[pos2] = temp;
}

// reverse the array in-place
void reverseArray(int arr[], int size) {
   int start = 0;
   int end = size-1;
   while (start < end) {
      swap(arr,start,end);
      start++;
      end--;
   }
}

// display the array
void displayArray(int arr[],int size) {
   int i;
   for(i=0;i<size;i++)
      cout<<arr[i]<<" ";
   cout<<endl;
}

// main
int main() {
   int arr[] = {1,52,45,3,9};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"\nOriginal Array :-";
   displayArray(arr,size);
   reverseArray(arr,size);
   cout<<"\nReversed Array :-";
   displayArray(arr,size);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j – i ) s.t arr(j) > arr(i)
About    Contact    Sitemap    Terms    Privacy