# Kth Largest Element in an Array

Given an integer array `nums` and an integer `k`, return *the* `kth` *largest element in the array*.

Note that it is the `kth` largest element in the sorted order, not the `kth` distinct element.

Can you solve it without sorting?

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [3,2,1,5,6,4], k = 2
</strong><strong>Output: 5
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
</strong><strong>Output: 4
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= k <= nums.length <= 105`
* `-104 <= nums[i] <= 104`

### Solutions

#### Approach - Brute Force Technique

```csharp
public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        
        Array.Sort(nums);
        k=nums.Length-k;
        return nums[k];
        
    }
}
```

Complexity

Time Complexity: O(n log n)

Space Complexity: O(1)

#### Approach - Min Heap Technique

```csharp
public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        // Create a Min Heap
        SortedSet<(int num, int index)> minHeap = new SortedSet<(int num, int index)>();
        int i = 0;
        // Add the first 'k' numbers in the min heap
        for (; i < k; i++)
            minHeap.Add((nums[i], i));

        // Go through the remaining numbers of the array, if the number from the array is bigger than the
        // top (smallest) number of the min-heap, remove the top number from heap and add the number from array
        for (; i < nums.Length; i++) {
            if (nums[i] > minHeap.Min.num) {
                minHeap.Remove(minHeap.Min);
                minHeap.Add((nums[i], i));
            }
        }

        // The root of the heap has the 'Kth' largest number
        return minHeap.Min.num;
    }
}

```

Complexity

Time Complexity: O(n log k)

Space Complexity: O(k)
