# Arrays

## Preserve indices while sorting array

Introduction This is a request from one of the readers. This is mostly useful in competitive programming where you want to sort an array by the values, but at the same time the requirement is to preserve the index of each element. If I have to explain using an example, then consider the array below. The array is zero indexed. The first two rows represent the input array and indices of each element in the array. The next two rows represent the sorted array, but the moment you sort it, the index for each element changes. Earlier A was at index 4 but in the sorted array it is at index ...

## Pair of Numbers to obtain given sum

Introduction This problem is already defined in one of the previous post. You can read that to know the problem in more detail. The definition goes like this, find a pair of numbers to obtain given sum in an array. The task is to find two numbers in an array which when added will produce a desired sum. Approach to find a Pair of Numbers to obtain given sum As the theory is already mentioned in the previous post, let us directly jump to all possible solutions. Here I am defining three different solutions to this problem. And the idea is to build a basic understanding and then proposing the b...

## Rotating an Array by a fixed distance

Problem Statement Another question which is favorite among interviewers is rotating an array by a fixed distance. Before understanding how can we do that, it is important to understand what it means to rotate an array. Given an array of length N, rotation by a fixed distance K means shifting each element to the right by K indices. The indices of course are computed in a rotational manner such that if the new index of the element goes beyond the array boundaries, it can be wrapped to the beginning of the array. Here is an example of input and output. The problem seems very easy until s...

## Find the Point of Rotation in Sorted Array

Problem Statement You are given a sorted array. However, there is a problem. Someone just rotated the sorted array by K spaces and we do not know the value of K. Write a program to find the value of K by which the array is rotated. As the array has millions of numbers, it would be good to have a solution which takes minimal time. Approach to Find the Point of Rotation Brute Force Let us try out my favorite approach, the Brute Force Method. It is quite simple, below are the steps: Start traversing the array from the beginning There will be a index in the array where the value sto...

## Find the maximum possible profit

Problem Statement Given an array of stock prices per share for a given share over a time period. Calculate the maximum possible profit per share one could have made . Here we do not consider short selling as an option. The trader must have purchased the stocks before selling it. The problem statement is a real world definition of the problem called maximum positive difference. For the above two arrays, here are the maximum profit per share one could have made: A : 18.0 (difference between 21 and 3) B : 13.0 (difference between 19 and 6) What is Maximum Positive Difference? ...