Need some help on this interview question

[Phil15]

Hi guys,

So I read this interview question:

"Given an array of integers, delete the max and min numbers (both could appear more than once) in place. Do it in O(n) without shifting. "

People provided answers such as : "if you hit the min or max you ignore it"..
but I am not convinced.


Logically I would answer in code below, but I am not convinced my answer would be correct, I am not removing elements just overwriting ..

So question is there a way to make an element in int array not a number or remove it all together? (Arrays are sequential though so how would you ever do that?)

int main()
{

	int arrOfIntegers[]{ 6,7,5,4,1,9,1,8,1,4,11,5,4,7,8,6,9,10 };

	int size = sizeof(arrOfIntegers) / sizeof(arrOfIntegers[0]);

	int max = arrOfIntegers[0];
	int min = arrOfIntegers[0];

	for (int i = 0; i <size; i++)
	{
		if (arrOfIntegers[i] < min)
		{
			min = arrOfIntegers[i];
		}

		if (arrOfIntegers[i] > max)
		{
			max = arrOfIntegers[i];
		}
	}


	for (int i = 0; i < size; i++)
	{

		if (arrOfIntegers[i] == min)
		{
			arrOfIntegers[i] = INT_MIN;

		}

		if (arrOfIntegers[i] == max)
		{
			arrOfIntegers[i] = INT_MIN;
		}

	}


	for (int i = 0; i < size; i++)
	{
		std::cout << arrOfIntegers[i] << std::endl;
	}


	system("pause");

}

	

[CptJY]

A option could be the use of a vector<int> :

#include <vector>

(replace the second and third for loop by )

	
...
	std::vector<int> v;
	
	for (unsigned int i = 0; i < size; i++)
	{   
	    if (arrOfIntegers[i] != max && arrOfIntegers[i] != min)
            	v.push_back(arrOfIntegers[i]);
	}

	for (unsigned int i = 0; i < v.size(); i++)
	{
		std::cout << v[i] << std::endl;
	}

another could be to store the result in another array.

[Phil15]

A option could be the use of a vector<int> :

#include <vector>

(replace the second and third for loop by )
std::vector<int> v;

for (unsigned int i = 0; i < size; i++)
{
if (arrOfIntegers[i] != max && arrOfIntegers[i] != min)
v.push_back(arrOfIntegers[i]);
}

for (unsigned int i = 0; i < v.size(); i++)
{
std::cout << v[i] << std::endl;
}


another could be to store the result in another array.

that`s what I though originally, but this is not in place though.

[jlb]

You can swap the "last" element with the minimum or maximum value and decrease the "size" of the array.

Where "last" is the last unswapped value and "size" decreases when you swap the elements.

Something like:

#include <iostream>
#include <algorithm>

int main()
{
    int arrOfIntegers[]{ 6,7,5,4,1,9,1,8,1,11,4,5,4,7,8,6,9,11,3 };

    size_t size = sizeof(arrOfIntegers) / sizeof(arrOfIntegers[0]);
    int min = *std::min_element(arrOfIntegers, arrOfIntegers + size);
    int max = *std::max_element(arrOfIntegers, arrOfIntegers + size);

    std::cout << min << " " << max << std::endl;

    for(size_t i = 0; i < size; ++i)
    {
        if(arrOfIntegers[i] == min)
            std::swap(arrOfIntegers[i], arrOfIntegers[(size--) - 1]);
        if(arrOfIntegers[i] == max)
            std::swap(arrOfIntegers[i], arrOfIntegers[(size--) - 1]);
    }

    for(size_t i = 0; i < size; ++i)
        std::cout << arrOfIntegers[i] << ' ';
    std::cout << std::endl;
    
    return 0;
}

[JLBorges]

Erase-remove idiom:

void remove_min_max( std::vector<int>& seq ) // O(N)
{
    if( seq.empty() ) return ;

    // find the smallest and the largest number - O(N)
    // http://en.cppreference.com/w/cpp/algorithm/minmax_element
    const auto min_max = std::minmax_element( std::begin(seq), std::end(seq) ) ;
    const int minv = *min_max.first ;
    const int maxv = *min_max.second ;

    // move all numbers equal to the mallest or largest value to the end of the sequence,
    // return a past-the-end iterator for the new end of the range of the remaining numbers - O(N)
    // http://en.cppreference.com/w/cpp/algorithm/remove
    const auto iter = std::remove_if( std::begin(seq), std::end(seq),
                                      [minv,maxv] ( int v ) { return v == minv || v == maxv ; } ) ;

    // erase the moved elements at the end of the sequence - O(N)
    // http://en.cppreference.com/w/cpp/container/vector/erase
    seq.erase( iter, std::end(seq) ) ;
}

http://coliru.stacked-crooked.com/a/a863094303b1d74d

[Phil15]

Brilliant, I knew there was a good answer, Thank you!