Very Easiest Approach | C++ | Sorting | Vector Pair

So the question's hint is available in the explanation itself. So our approach would look something like this.

Approach:

  1. At any given point we should know our smallest element in our array ( hint : maybe we can use sorting / heap)
  2. Also we should be knowing where the minimum number is present at any given moment (hint : we must store in a pair)
  3. So, when we process the array / heap, we will pop their value and index, and have a boolean flag array, to mark its left and right, so that when we iterate over the array / heap, we must know which value to add in our answer.

**Input**: nums = [2,1,3,4,5,2]

We will use array with pairs and store the value and its corresponding index in the array.
Our array would look something like this
[{2,0}, {1,1}, {3,2}, {4,3}, {5,4}, {2,5}]

We will sort this array and then traverse it by checking the flag condition. So the code would look something like this

class Solution {
public:
    long long findScore(vector<int>& nums) {
        long long ans = 0;
        int n = nums.size();
        vector<pair<int,int>> v;
        vector<bool> flag(n,false);
        
        for(int i=0;i<n;i++)
        {
            v.push_back({nums[i] , i});
        }
        sort(v.begin(),v.end());
        
        for(int i=0;i<n;i++)
        {
            int val = v[i].first;
            int ind = v[i].second;
            if(!flag[ind])
            {
                flag[ind] = true;
                if(ind - 1 >= 0)
                {
                    flag[ind-1] = true;
                }
                if(ind + 1 < n)
                {
                    flag[ind+1] = true;
                }
                ans += val;
            }
            
        }
        return ans;
    }
};

Do UpVote or comment if there are any doubts or correction :D

Comments (0)