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)

DEV

Thank you.

 
Thanks for visiting DEV, we’ve worked really hard to cultivate this great community and would love to have you join us. If you’d like to create an account, you can sign up here.