Function returning the wrong kth value while using sets

Question

I was attempting to solve this question on some website where you have the find the kth smallest value in c++ so I came up with:

#include <bits/stdc++.h>
using namespace std;
int kthSmallest(int arr[], int l, int r, int k) {

    // l is the first index 
    // r is the index of the last element (size - 1)
    // k is the kth smallest value 
    set<int> s(arr, arr + r); 

    
    set<int>:: iterator itr = s.begin();
    advance(itr, (k - 1));
    
    return *itr;
}
int main() {
  int arr[] = {7, 10, 4, 20, 15};
  cout << kthSmallest(arr, 0, 4, 4);
  return 0;
}

This shows the output of 20 instead of 15 which is the right answer and I cannot figure out what I did wrong here.

You do know that [std::nth_element](https://en.cppreference.com/w/cpp/algorithm/nth_element) does this already? — PaulMcKenzie, Jul 11 '22 at 19:08
Side note: Careful with the combination of `#include ` and `using namespace std;`. Separately they are dangerous ([why](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [why](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)) , but together they amplify the other's worst effects and can result in nigh-inscrutable errors. — user4581301, Jul 11 '22 at 19:15
[Using std::nth_element](http://coliru.stacked-crooked.com/a/74e8f2e638519bb6). — PaulMcKenzie, Jul 11 '22 at 19:19
You can make your work much easier by [learning to use a debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). A debugger would have shown you that `set s(arr, arr + 4);` creates a set of _four_ elements. — Drew Dormann, Jul 11 '22 at 19:23

score 0 · Accepted Answer · answered Jul 11 '22 at 19:10

The 2nd argument of the constructor of std::set should be an iterator for an element next to the last element, not one for the last element.

Therefore, you are operating with a set whose members are {7, 10, 4, 20}.

The line

set<int> s(arr, arr + r);

should be

set<int> s(arr, arr + r + 1);

or (to match the comment)

set<int> s(arr + l, arr + r + 1);

Vlad from Moscow · Answer 2 · 2022-07-11T20:17:49.547

The range in this statement

set<int> s(arr, arr + r);

is specified incorrectly when r is equal to 4 for this array

int arr[] = {7, 10, 4, 20, 15};

that has 5 elements. It means that 15 is not present in the range [7, 10, 4, 20]. You have to specify the parameter r equal to 5 that is to the number of elements in the array instead of 4.

Also the parameter l is not used in the function.

And you need to check whether the value of k is not greater than the value of r calling the function std::advance.

Also pay attention to that the array can have duplicated values. In this case the function can return an incorrect value.

So in general your function is incorrect and unsafe.

Instead of returning an object of the type int you should return either an iterator that points to the target object in the array or to the end of the range or the index of the target element..

With your approach you should use std::multiset instead of std::set. And the value of k should start from 0 as all indices in C++. Otherwise calling the function with the value of k equal to 0 you will get undefined behavior.

Here is a demonstration program.

#include <iostream>
#include <functional>
#include <set>
#include <iterator>

size_t kthSmallest( const int arr[], size_t n, size_t k ) 
{
    if ( not ( k < n ) ) return n;

    std::multiset<std::reference_wrapper<const int>> s;

    for ( size_t i = 0; i < n; i++ )
    {
        s.insert( std::ref( arr[i]) );
    }

    auto it = std::next( std::begin( s ), k );

    size_t result = std::distance( arr, &it->get() );

    return result;
}    

int main() 
{
    int arr[] = {7, 10, 4, 20, 15};
    const size_t N = sizeof( arr ) / sizeof( *arr );

    for ( size_t i = 0; i < N; i++ )
    {
        std::cout << i << ": " << arr[kthSmallest( arr, N, i )] << '\n';
    }

    return 0;
}

The program output is

The array `arr` doesn't have 6 elements. – MikeCAT Jul 11 '22 at 19:12 — MikeCAT, Jul 11 '22 at 19:12

Function returning the wrong kth value while using sets

2 Answers2