How to make an O (N) runtime out of O (N ^ 2)
I tried to solve one programming problem (neither my homework nor my interview / test, but might be a good candidate) on the internet. The problem is listed below. My code below is functionally correct, but it has a runtime complexity of O (N 2 ) where the solution is expected to be in O (N).
I tried a couple of other approaches to optimize it. 1) Sorted the array and then tried if I could process it, but since sorting results in losing the indices of the original numbers, I even saved them in a separate array, and did so, but even that turned out to be O (N 2 ). I'm sure sorting the array will get you O (N) here, but just won't be able to nail it.
Any help on solving this in O (N) using any approach would be helpful.
(Apologies for the long post)
Consider the zero index A of N integers. The indices of this array are integers from 0 to N-1. Take the index K. The index J is called the erection of A if A [J]> A [K]. Note that if A [K] is the maximum value in array A, then K has no ascending lines.
Ascender J of K is called the closest clamping element K if abs (KJ) is the smallest possible value (i.e. if the distance between J and K is minimum). Note that K can have at most two closest ascending lines: one less and one greater than K.
For example, consider the following array A:
A [0] = 4 A [1] = 3 A [2] = 1 A [3] = 4 A [4] = -1 A [5] = 2 A [6] = 1 A [7] = 5 A [8] = 7
If K = 3, then K has two ascending ones: 7 and 8. Its closest clamp is 7, and the distance between K and 7 is abs (K-7) = 4.
Write a function:
struct Results {
int * R;
int N;
};
struct Results array_closest_ascenders(int A[], int N);
which, given the zero index A of N integers, returns the zero index R of N integers, such that (for K = 0, ..., N-1):
if K has the closest ascender J, then R[K] = abs(KβJ); that is, R[K] is equal to the distance between J and K,
if K has no ascenders then R[K] = 0.
For example, given the following array A:
A [0] = 4 A [1] = 3 A [2] = 1 A [3] = 4 A [4] = -1 A [5] = 2 A [6] = 1 A [7] = 5 A [8] = 7
the function should return the following R array:
R [0] = 7 R [1] = 1 R [2] = 1 R [3] = 4 R [4] = 1 R [5] = 2 R [6] = 1 R [7] = 1 R [ 8] = 0
The R array should be returned as:
a structure Results (in C), or
a vector of integers (in C++), or
a record Results (in Pascal), or
an array of integers (in any other programming language).
Let's pretend that:
N is an integer within the range [0..50,000];
each element of array A is an integer within the range [β1,000,000,000..1,000,000,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
The elements of the input arrays can be changed.
My solution (O (N 2 )):
#include <math.h>
#include "stdio.h"
#include "stdlib.h"
struct Results
{
int *R;
int N;
};
struct Results array_closest_ascenders ( int A[], int N )
{
struct Results result;
int i,j,asc_found=0;
result.R = (int*)malloc(sizeof(int)*N);
for(i=0;i<N;i++)
result.R[i] = N;
result.N = N;
for(i=0;i<N;i++)
{
asc_found = 0;
for(j=0;j<N;j++)
{
if(A[i] < A[j])
{
//if(result.R[i] == 0)
{
if(result.R[i] > abs(i-j))
{
result.R[i] = abs(i-j);
asc_found = 1;
}
}
}
}
if(asc_found == 0)
result.R[i] = 0;
}
return result;
}
void main()
{
//int A[] = {4, 3, 1, 4, -1, 2, 1, 5, 7};
int A[] = {691446939, -241956306, 485954938, 604054438, 383714185, -656099986, -357341170, -255988102, -139683363, -463281394, -382925609, 712727854};
struct Results tmp;
tmp = array_closest_ascenders(A,sizeof(A)/sizeof(A[0]));
}
source to share
The closest left clamp and the closest right clamp can be viewed separately. We walk through the array once, calculating the nearest left-hand ascending lines; and again in the opposite direction, calculating the right-hand nearest ascents. The nearest spotlight is closer to each other.
In the algo below, only the left elevations are considered. The index stack keeps track of the left ascending lines (all of them) of the current item. The closest clamp is always at the top of the stack.
for i in 0 .. N
while (!stack.empty) && (A[stack.top] <= A[i])
stack.pop
if stack.empty
then R[i] = 0
else R[i] = i - stack.top
stack.push(i)
source to share
I want to add this as a comment, but there is no link to the comment. Should R [] follow?
R[0]=abs(0-7)=7;
R[1]=abs(1-0)=1;
R[2]=abs(2-5)=3;
R[3]=abs(3-7)=4;
R[4]=abs(4-2)=2;/or 4-6
R[5]=abs(5-1)=4;
R[6]=abs(6-5)=1;
R[7]=abs(7-8)=1;
R[8]=abs(8-8)=0;
Based on your comment below, here's a program that works. The algorithm is based on sorting counting (as shown at http://geekviewpoint.com/Sort_Algorithms_in_java/ ). "Offset" must allow negative values ββsuch as "-1"
NOTE. Despite having a nested loop to fill R [], the algorithm is not N ^ 2 because the second loop iterates over the number of buckets.
ANSWER: [7, 1, 1, 4, 1, 2, 1, 1, 0]
import java.util.ArrayList;
import java.util.Arrays;
public class Ascender {
public static int[] ascenderArray(int[] A) {
int max = A[0], min = A[0];
for (int i : A) {
if (max < i)
max = i;
if (min > i)
min = i;
}
int offset = min < 0 ? -min : 0;
ArrayList<Integer> buckets[] = new ArrayList[max + 1 + offset];
for (int i = 0; i < buckets.length; i++)
buckets[i] = new ArrayList<Integer>();
for (int i = 0; i < A.length; i++)
buckets[A[i] + offset].add(i);
int[] R = new int[A.length];
for (int i = 0; i < R.length; i++) {
try {
min = A.length;
int x = A[i] + 1 + offset;
for (int n = x; n < buckets.length; n++) {
x=n;
while (buckets[x].isEmpty())
x++;
n=x;
int tmp = Math.abs(i - buckets[n].get(0));
if (min > tmp)
min = tmp;
}
R[i] = min==A.length?0:min;
} catch (Exception e) {
R[i] = 0;
}
}
return R;
}//
public static void main(String... args) {
int A[] = { 4, 3, 1, 4, -1, 2, 1, 5, 7 };
int R[] = ascenderArray(A);
System.out.println(Arrays.toString(R));
}
}
source to share
I'm not sure if there is a Ξ (N) solution, but there is a Ξ (N log N) solution in JavaScript:
var A = [4,3,1,4,-1,2,1,5,7],
N = A.length;
// build an array of index:value pairs and sort them in ascending order
var sorted = [];
for (var i=0; i<N; i++) {
sorted.push({index:i, value:A[i]});
}
sorted.sort(function(a, b) { return a.value - b.value; });
// iterate the sorted array in descending order
var ascenders = [],
closest, // closest ascender
curr = sorted[N-1]; // initiate curr with largest item
ascenders[N-1] = 0;
for (var i=N-2; i>=0; i--) {
// compare curr from the previous iteration with the future
// curr of the current iteration
if (sorted[i].value !== curr.value) {
// update closest ascender if their values differ
closest = curr;
}
curr = sorted[i];
ascenders[i] = Math.abs(curr.index-closest.index);
}
// rearrange ascenders in the original order
var ret = [];
for (var i=0; i<N; i++) {
ret[sorted[i].index] = ascenders[i];
}
Here, sorting the values ββis the greatest effort Ξ (N log N).
source to share
import java.util.Arrays;
import java.util.TreeMap;
public class AsenderUtil {
public static int[] getClosestAsenderIndices(int[] arr, int indx) {
if (indx < 0 || arr.length <= indx)
throw new RuntimeException("wrong input");
int baseVal = arr[indx];
TreeMap<Integer,Integer> ts = new TreeMap<Integer,Integer>();
for(int i=0;i<arr.length;i++){
if(arr[i]>baseVal) {
ts.put(Math.abs(i-indx),i);
}
}
int[] toReturn = new int[2];
toReturn[0] = ts.remove(ts.firstKey());
toReturn[1] = ts.remove(ts.firstKey());
return toReturn;
}
public static void main(String... args) {
int A[] = { 4, 3, 1, 4, -1, 2, 1, 5, 7 };
int R[] = getClosestAsenderIndices(A,3);
System.out.println(Arrays.toString(R));
}
}
source to share
class Program
{
static void Main(string[] args)
{
int[] A = new int[] { 4, 3, 1, 4, -1, 2, 1, 5, 7 };
int[] B = new int[A.Length];
int[] R = new int[A.Length];
Program obj = new Program();
obj.ABC(A,B, R);
}
public void ABC(int[] A,int[]B, int[] R)
{
int i, j, m,k;
// int temp = 0;
int n = A.Length - 1;
for (i = 0; i < n; i++)
{
for (j = 0; j <= n; j++)
{
if (A[i] < A[j])
{
m = Math.Abs(j - i);
R[i] = m;
break;
}
}
for (j = i-1; j > 0; j--)
{
if (A[i] < A[j])
{
k = Math.Abs(j - i);
B[i] = k;
break;
}
}
}
for (i = 0; i < n; i++)
{
if (R[i] > B[i] && (B[i] == 0))
{
R[i] = R[i];
//Console.WriteLine(R[i]);
//Console.ReadLine();
}
else { R[i] = B[i]; }
}
}
}
source to share
My solution is O (N):
class ArrayClosestAscendent {
public int[] solution(int[] A) {
int i;
int r[] = new int[A.length];
for(i=0;i<A.length;i++){
r[i] = search(A, i);
}
return r;
}
public int search(int[] A, int i) {
int j,k;
j=i+1;
k=i-1;
int result = 0;
if(j <= A.length-1 && (A[j]>A[i]))
return Math.abs(j-i);
j++;
while(k>=0 || j < A.length){
if(k >= 0 && A[k] > A[i]){
return Math.abs(i-k);
}else if(j < A.length && A[j] > A[i]){
return Math.abs(i-j);
}else{
j++;
k--;
}
}
return result;
}
}
Basically in the search function I am comparing the first element of the array with the one immediately to the right, if it is larger it means that it is the first closest ascending one. For other elements, I compare the one immediately to the left and then the one that immediately directs its first right-hand element. The first one, which is larger, is the closest ascending one, and I keep iterating that way until I find an element that is larger than the one I am considering, or I return 0.
source to share