Why stoi() function is not working in the following code?

Question

class Solution {
public:
    string kthLargestNumber(vector<string>& nums, int k) {
        priority_queue<int>q;
        for(int i=0;i<nums.size();i++)
        {
            q.push(stoi(nums[i]));
        }
        while(!q.empty())
        {
                k--;
                if(k==0)
                {
                    return q.top();
                }
                q.pop();
        }
        return 0;   
    }
};

I was trying to solve Leetcode 1985. Find the Kth Largest Integer in the Array problem. But I am having a Compile Error at line no 14 ( return q.top(); ) I don't know why this happening.

Problem Link

Answer 1

Just looking at the code, the answer would be simple. The function should return an std::string and you return and int. You could be tempted now to solve the issue by using the to_string function and convert the int to a std:string.

But, this will not work.

The solution should and must work with strings.

Constraints:
    1 <= k <= nums.length <= 104
    1 <= nums[i].length <= 100
    nums[i] consists of only digits.
    nums[i] will not have any leading zeros.

It is obvious that you cannot store 100 digits long numbers in an int. So, you must also use sorting with strings.

But this will make life difficult, because you then need to employ so called natural sorting.

Example: Looking a 2,3 and 200, then, if you compare string, 3 will be greater than 200. And that is what the guys want from you. Natural sorting.

There are many solutions possible. Here is one of them:

#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std::string_literals;

// FUNCTOR for Natural sort function. Limited to signed char strings
struct NaturalSort {

    bool operator ()(const std::string& s1, const std::string& s2) {

        // We want to iterate over both strings
        const char* i1 = s1.data(); // Get a pointer to the beginning of string 1
        const char* i2 = s2.data(); // Get a pointer to the beginning of string 2

        // Result of comparison. 0 means equal, positive means s1>s2, negative means s1<s2
        int result = 0;
        // As long as both characters/numbers are equal and there are still characters in the string
        do {
            // If we found a digit at the same position in both strings
            if (std::isdigit(*i1) and std::isdigit(*i2)) {

                std::size_t pos1{}, pos2{}; // This will later indicate how many digits we read
                // Convert the strings to numbers and compare them
                result = std::stoi(i1, &pos1) - std::stoi(i2, &pos2);
                // Set pointers to the position after the number
                i1 += pos1; i2 += pos2;
            }
            else {
                // Normal character
                result = (*i1 - *i2);
                ++i1; ++i2;
            }
        } while ((result == 0) and (*i1 != 0 or *i2 != 0));
        // Let's limit the output to -1, 0 ,1
        return result < 0;
    }
};


class Solution{
public:
    std::string kthLargestNumber(std::vector<std::string>& nums, int k) {
        std::sort(nums.begin(), nums.end(), NaturalSort());
        return nums[nums.size()-k];
    }
};

// Driver / test code
int main() {
    std::vector<std::string> test{ "2"s,"3"s,"20"s,"30"s,"200"s,"300"s };
    Solution solution{};
    for (int k = 1; k <= test.size(); ++k) 
        std::cout << "With k=" << k << " the result would be: " << solution.kthLargestNumber(test, k) << '\n';
}