C++, O(n) time, O(1) extra space

  • 9
    class Solution {
    vector<int> productExceptSelf(vector<int>& nums) {
        int k = nums.size();
        vector<int> res(k,1);
        for (int i=1;i<k;i++){
        int temp = 1;
        for (int i=k-1;i>=0;i--){
        return res;

  • -1

    I don't think this is O(1) extra space since you are using result vector as a temporary working space for calculating product accumulated from one direction,

  • 0

    I agree what you said, but the problem says (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

  • 0

    Good alg, I see such a solution for first time(maybe I am naive now), thank you

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.