Interview Question: Kth Smallest and Largest Element of Array C++

Kartikeya Mishra
3 min readOct 21, 2023

--

Company Interviews Using C++ Data Structures and Algorithms

#include <algorithm>
#include <vector>
#include <iostream>

vector<int> kthSmallLarge(vector<int> &arr, int n, int k)
{
sort(arr.begin(), arr.end());
return{arr[k-1], arr[n-k]};


}

English :

This code defines a function named kthSmallLarge. It takes the following parameters:

  1. arr: A reference to a vector of integers (std::vector<int> &arr). This vector contains the elements to be sorted and from which we will find the k-th smallest and k-th largest elements.
  2. n: An integer representing the size of the input vector.
  3. k: An integer representing the desired position in the sorted vector.

Here’s how the function works:

  1. It sorts the input vector arr using the sort function, which rearranges the elements in ascending order (from smallest to largest).
  2. It returns a vector with two elements. The first element, arr[k - 1], represents the k-th smallest element in the sorted array. The second element, arr[n - k], represents the k-th largest element in the sorted array.

The subtraction of 1 from k is done because C++ vectors are zero-based (the first element is at index 0), so to find the k-th smallest element, we subtract 1 from k to access the correct index.

Hindi :

यह कोड एक फ़ंक्शन को kthSmallLarge के नाम से परिभाषित करता है। इसमें निम्नलिखित पैरामीटर होते हैं:
arr: पूरी तरह के पूर्णांक वेक्टर का संदर्भ (std::vector<int> &arr)। इस वेक्टर में उन तत्वों को सॉर्ट करने के लिए होते हैं, जिनसे हम k-वें सबसे छोटा और k-वें सबसे बड़ा तत्व ढूंढ़ेंगे।
n: एक पूर्णांक जो इनपुट वेक्टर के आकार को प्रतिनिधित करता है।
k: एक पूर्णांक जो सॉर्ट किए गए वेक्टर में इच्छित स्थिति को प्रतिनिधित करता है।

यहां यह दिखाया जाता है कि फ़ंक्शन कैसे काम करता है:
यह सॉर्ट फ़ंक्शन का उपयोग करके इनपुट वेक्टर arr को सॉर्ट करता है, जिसमें तत्वों को आरोही क्रम में पुनः व्यवस्थित करता है (सबसे छोटे से सबसे बड़े तक)।
यह दो तत्वों वाले एक वेक्टर को लौटाता है। पहला तत्व, arr[k — 1], सॉर्ट किए गए वेक्टर में k-वें सबसे छोटे तत्व का प्रतिनिधित करता है। दूसरा तत्व, arr[n — k], सॉर्ट किए गए वेक्टर में k-वें सबसे बड़े तत्व को प्रतिनिधित करता है।

k से 1 कम करने का कार्य किया जाता है क्योंकि C++ वेक्टर शून्य-मूल आधारित होते हैं (पहला तत्व सूची में सूची 0 पर होता है), इसलिए k-वें सबसे छोटे तत्व को खोजने के लिए k से 1 कम करके सही सूची में पहुँचने के लिए।

Hinglish :

Is code mein ek function ko kthSmallLarge naam se define kiya gaya hai. Ismein neeche diye gaye parameters liye gaye hain:

1. `arr`: Integer vectors ka ek reference (std::vector<int> &arr). Is vector mein woh elements hain jo sort kiye jayenge, aur jinse ham k-th smallest aur k-th largest elements nikalenge.
2. `n`: Input vector ki size ko represent karne wala ek integer.
3. `k`: Sorted vector mein chahiye hue position ko represent karne wala ek integer.

Yahaan tak is function ka kaam kaise karta hai:

1. Yeh input vector `arr` ko `sort` function ka istemal karke sort karta hai, jo elements ko chhote se bade order mein rakhta hai.

2. Yeh ek vector ko return karta hai jismein do elements hote hain. Pehla element, `arr[k — 1]`, sorted array mein k-th smallest element ko represent karta hai. Dusra element, `arr[n — k]`, sorted array mein k-th largest element ko represent karta hai.

`k` se 1 ka subtraction tab kiya jata hai kyun ki C++ vectors zero-based hote hain (pehla element index 0 par hota hai), isliye k-th smallest element ko dhundhne ke liye, k se 1 subtract kiya jata hai tak sahi index tak pahuncha jaa sake.

--

--

Kartikeya Mishra
Kartikeya Mishra

Written by Kartikeya Mishra

Computer science engineer nomad exploring digital world. Learning and teaching while having fun.