The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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)