DEV Community

Mayank Arora
Mayank Arora

Posted on

724. Find Pivot Index [Leetcode][C++]

All suggestions are welcome. Please upvote if you like it. Thank you.


Leetcode Problem Link: 724. Find Pivot Index


Brute Force Solution:

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
    // Brute Force Solution Time O(N^2) & Auxiliary Space O(1)
    // Calculate the sum of elements to the left & right
    // of each index of nums vector and compare them to check equivalence
    int len=nums.size();
    if(len==1)
        return nums[0];
    for(int i=0;i<len;i++){
         // accumulate() takes O(N) time and for loop runs for n iterations.
         // So time taken by for loop is O(n*n)=O(N^2)
          int left=accumulate(nums.begin(),nums.begin()+i,0); 
          int right=accumulate(nums.begin()+i+1,nums.end(),0);
          if(left==right)
              return i;
    }
      return -1;
    }
};

Enter fullscreen mode Exit fullscreen mode

Efficient Solution:

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
    // Efficient Solution Time O(N) & Auxiliary Space O(1)
    // Create a sum array in which each element stores 
    // the sum of elements of nums vector up to that index.
    // Calculate left & right sum. For example-
    // nums[]=[1,7,3,6,5,6]
    // sum[]= [1,8,11,17,22,28]
    // left[3]=17-6=11
    // right[3]=28-17=11
    // return 3
    int len=nums.size();
    if(len==1)
        return 0;
    int sum[len];
    sum[0]=nums[0];
    for(int i=1;i<len;i++){
        sum[i]=nums[i]+sum[i-1];
    }
    for(int i=0;i<len;i++)
    {
        int left=sum[i]-nums[i];
        int right=sum[len-1]-sum[i];

    if(left==right)
        return i;
    }
      return -1;
    }
};

Enter fullscreen mode Exit fullscreen mode

All suggestions are welcome. Please upvote if you like it. Thank you.

Top comments (0)