We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Minimum Loss
  5. Discussions

Minimum Loss

  • ayushr2
     + 2 comments

    Hey! Well your solution is a little inefficient even though it passes the test cases. The reason being that in each iteration you are calling numbers.index which is O(n). Instead when you sort the array you can sort the indexes too along with the numbers. Look at what I have done. It makes numbers.index O(n). create an object which pairs up the index and number. then sort based on the number and indexes also get sorted along with it. My solution is O(n) while yours maybe O(n^2).

    #include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct pair_custom {
        long num;
        int index;
    };

struct {
        bool operator() (pair_custom one, pair_custom two) {
            return one.num > two.num;
        }
    } custom;
    
int main() {
    int n;
    cin >> n;
    vector<pair_custom> arr;
    long temp_max = 0;
    long answer;
    for(int i = 0; i < n; i++) {
        pair_custom cur;
        cin >> cur.num;
        cur.index = i;
        arr.push_back(cur);

        if (cur.num > temp_max) {
            temp_max = cur.num;
        } else {
            answer = temp_max - cur.num;
        }
    }
    sort(arr.begin(), arr.end(), custom);
    
    for(int i = 0; i < n - 1; i++) {
        if (arr[i].index < arr[i+1].index && (arr[i].num - arr[i+1].num) < answer) {
            answer = arr[i].num - arr[i+1].num;
        }
    }
    
    cout << answer;
    return 0;
}