"Max Min" in HackerRank

Question

I am trying to implement the solution for the problem "Max Min" in HackerRank. The solution runs for some test cases but for few test cases it pops out showing "Terminated due to Time Out"

Problem:

Given a list of \$N\$ integers, your task is to select \$K\$ integers from the list such that its unfairness is minimized.

Unfairness = Max{K integer Set} - Min{K integer Set}

where max denotes the largest integer among the elements of \$K\$, and min denotes the smallest integer among the elements of \$K\$.

Input Format

• The first line contains an integer \$N\$.
• The second line contains an integer \$K\$.
• \$N\$ lines follow. Each line contains an integer that belongs to the list \$N\$.

Note: Integers in the list \$N\$ may not be unique.

Output Format

An integer that denotes the minimum possible value of unfairness.

Constraints

• \$2 \le N \le 10^5\$
• \$2 \le K \le N\$
• \$0 \le \text{integer in} N \le 10^9\$

Sample Input #00

7
3
10
100
300
200
1000
20
30

Sample Output #00

20

Can anyone please point to me which part of my code is taking longer to implement and what a better solution can be?

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

#define MAX 100000
#define MAX_VAL 1000000001

int list[MAX];

int main() {

    int N, K;
    int i;
    int unfairness=0;
    scanf_s("%d %d", &N, &K);
    int set = K - 1;
    for (i = 0; i < N; i++)
        scanf_s("%d", &list[i]);
    for (int l = 0; l < N - 1; l++){
        for (int j = 0; j < N - l - 1; j++)
        {
            if (list[j] > list[j + 1])
            {
                int temp;
                temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
    for (int x = 0; x < N - set; x++)
    {
        int differ = list[x + set] - list[x];
        //printf("Dif - %d\n", differ);
        //printf("Unfair - %d\n", unfairness);
        if (unfairness == 0){
            unfairness = differ;
        }
        else if (differ<unfairness)
            unfairness = differ;
    }
    printf("%d", unfairness);
    return 0;
}

Answer 1

The slowness comes from the sort algorithm you've chosen. It's \$O(N^2)\$ and you can do better by using a faster sort algorithm, such as merge sort or quicksort. Once you do that, the solution will pass with flying colors.

---

You could simplify the loop that checks the maximum difference by initializing unfairness to the diff of the first interval:

int unfairness = list[set] - list[0];

And then start the loop from 1, and simplify:

for (int x = 1; x < N - set; x++) {
    int diff = list[x + set] - list[x];
    if (diff < unfairness) {
        unfairness = diff;
    }
}

Also, it would be good to put this code in a separate function. It's good to have many short functions that do one thing, than one long function that does many things.

---

Instead of initializing i at the top of the function, it would be better to do that inside the for-loop where you use it, just like you did for other loops.

I recommend to avoid using l as a variable name, because on some displays and fonts it's too hard to distinguish from 1 or I.