Find the Kth Largest Integer in the Array

Find the Kth Largest Integer in the Array - Problem

Array String Divide and Conquer Sorting Heap (Priority Queue) Quickselect Medium

You are given an array of strings nums and an integer k. Each string in nums represents an integer without leading zeros.

Return the string that represents the kth largest integer in nums.

Note: Duplicate numbers should be counted distinctly. For example, if nums is ["1","2","2"], "2" is the first largest integer, "2" is the second-largest integer, and "1" is the third-largest integer.

Input & Output

Example 1 — Basic Case

$ Input: nums = ["3","6","7","10"], k = 4

› Output: "3"

💡 Note: Sorted in descending order: ["10","7","6","3"]. The 4th largest is "3".

Example 2 — With Duplicates

$ Input: nums = ["2","21","12","1"], k = 3

› Output: "2"

💡 Note: Sorted: ["21","12","2","1"]. The 3rd largest is "2".

Example 3 — Large Numbers

$ Input: nums = ["1","2","2"], k = 2

› Output: "2"

💡 Note: Sorted: ["2","2","1"]. Both "2"s are counted distinctly, so 2nd largest is "2".

Constraints

1 ≤ k ≤ nums.length ≤ 10⁴
1 ≤ nums[i].length ≤ 100
nums[i] consists of only digits
nums[i] will not have any leading zeros

Visualization

Tap to expand

Understanding the Visualization

Input

Array of string numbers and target k

Sort

Sort strings by numeric value (not lexicographically)

Output

Return kth element from sorted array

Key Takeaway

🎯 Key Insight: String numbers need special comparison - longer strings are larger numbers, not lexicographic ordering

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is that string numbers can be compared directly using length and lexicographic order. For same-sign numbers, longer strings represent larger values, and for same-length strings, lexicographic comparison works. Best approach uses custom string comparator to sort efficiently. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Min Heap Approach	O(n log k)	O(k)	Use min heap to track top k elements
Sort All Elements	O(n log n)	O(n)	Convert strings to integers, sort, and return kth from end
Custom String Comparator	O(n log n)	O(1)	Sort strings directly using custom numeric comparator

Min Heap Approach — Algorithm Steps

Create min heap of capacity k
For each number, compare with heap minimum
Keep only k largest elements in heap
Return heap's minimum (kth largest)

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Heap

Add first k elements to min heap

Process

For remaining elements, compare with heap minimum

Result

Heap's minimum is kth largest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char** data;
    int size;
    int capacity;
} MinHeap;

int isSmaller(const char* a, const char* b) {
    int lenA = strlen(a);
    int lenB = strlen(b);
    if (lenA != lenB) {
        return lenA < lenB;
    }
    return strcmp(a, b) < 0;
}

MinHeap* createHeap(int capacity) {
    MinHeap* heap = malloc(sizeof(MinHeap));
    heap->data = malloc(capacity * sizeof(char*));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void heapifyUp(MinHeap* heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (!isSmaller(heap->data[index], heap->data[parent])) break;
        
        char* temp = heap->data[index];
        heap->data[index] = heap->data[parent];
        heap->data[parent] = temp;
        index = parent;
    }
}

void heapifyDown(MinHeap* heap, int index) {
    while (1) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap->size && isSmaller(heap->data[left], heap->data[smallest])) {
            smallest = left;
        }
        if (right < heap->size && isSmaller(heap->data[right], heap->data[smallest])) {
            smallest = right;
        }
        if (smallest == index) break;
        
        char* temp = heap->data[index];
        heap->data[index] = heap->data[smallest];
        heap->data[smallest] = temp;
        index = smallest;
    }
}

void heapPush(MinHeap* heap, char* value) {
    heap->data[heap->size] = malloc(strlen(value) + 1);
    strcpy(heap->data[heap->size], value);
    heapifyUp(heap, heap->size);
    heap->size++;
}

char* heapPop(MinHeap* heap) {
    char* result = heap->data[0];
    heap->size--;
    if (heap->size > 0) {
        heap->data[0] = heap->data[heap->size];
        heapifyDown(heap, 0);
    }
    return result;
}

char* solution(char** nums, int numsSize, int k) {
    MinHeap* heap = createHeap(k);
    
    for (int i = 0; i < numsSize; i++) {
        if (heap->size < k) {
            heapPush(heap, nums[i]);
        } else if (!isSmaller(nums[i], heap->data[0])) {
            free(heap->data[0]);
            heap->data[0] = malloc(strlen(nums[i]) + 1);
            strcpy(heap->data[0], nums[i]);
            heapifyDown(heap, 0);
        }
    }
    
    char* result = malloc(strlen(heap->data[0]) + 1);
    strcpy(result, heap->data[0]);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char** nums = malloc(1000 * sizeof(char*));
    int numsSize = 0;
    
    char* token = strtok(line, "[]\",");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            nums[numsSize] = malloc(strlen(token) + 1);
            strcpy(nums[numsSize], token);
            numsSize++;
        }
        token = strtok(NULL, "[]\",");
    }
    
    int k;
    scanf("%d", &k);
    
    char* result = solution(nums, numsSize, k);
    printf("%s\n", result);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log k)

Process n elements, each heap operation takes O(log k)

⚡ Linearithmic

Space Complexity

O(k)

Heap stores at most k elements

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

891 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Min Heap Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler