CODEWITHSUNDEEP
arrayskotlindata-structures
Vivek Modi
Vivek Modi

Reputation: 7181

Running Sum of 1d Array in kotlin

Hey guys I am learning data structure. I am trying to solve a problem of leetcode.

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

I tried my solution and it working fine and I understand all stuff.

My solution

class Solution {
    fun runningSum(nums: IntArray): IntArray { 
        if (nums.size == 1) {
            return nums
        }
        for (index in 1..nums.size - 1) {
            nums[index] += nums[index - 1]
        }
        return nums
    }
}

Complexity Analysis

Everything seems ok to me but I went to discuss section and I found one fold solution. So my question is there

  1. Is any complexity changes in this solution to my original solution?
  2. If yes, can you please explain me in details?
  3. Please explain me the use of foldIndexed because I didn't get it correctly. I read the doc as well.

Many Thanks.

Upvotes: 1

Views: 1362

Answers (3)

Anowar Hossain Anu
Anowar Hossain Anu

Reputation: 11

You can follow anyone.

First Way:

fun runningSum(nums: IntArray): IntArray{
    for ( index in 1 until nums.size){
        nums[index]+=nums[index-1]
    }
    return nums
}

Second Way:

fun runningSum(nums: IntArray): IntArray{
    var i = 0
    nums.fold(0) {sum, element ->
        nums[i++] = sum + element
        nums[i-1]
    }
    return nums
}

Third Way

fun runningSum(numbers: IntArray): IntArray {
    val numList = numbers.runningFold(0) { sum, num ->
        sum + num
    }.toMutableList()
    numList.removeFirst()
    return numList.toIntArray()
}

Upvotes: 0

xmutt
xmutt

Reputation: 141

You can do it in one line (line-broke for clarity):

return IntArray(nums.size).also {
    // "it" is the IntArray just created
    nums.forEachIndexed { i, v ->
        it[i] = it.getOrElse(i - 1) { 0 } + v
    }
    // "it" will be returned here
}

Upvotes: 0

Marco Kurepa
Marco Kurepa

Reputation: 300

There should be no change to the Time Complexity or Space Complexity when going from your solution to the other solution. So foldIndexed works the same way as fold with the key difference being that it also has an index. The programmer here chose foldIndexed because he was looking not for the sum at the end, but for the sum at each stage as it loops through the array, and he wanted to input them into the answers array. Knowing this, we can understand the essence of the code using fold instead. That'd look something like this:

fun runningSum(nums: IntArray): IntArray {
        val answers = IntArray(nums.size)

        nums.fold(0) {sum, element ->
            sum + element
        }

        return answers
    }

So going piece by piece, 0 is saying we're starting from the index 0 in the nums IntArray. sum is what is called an accumulator, which is basically a temporary variable within .fold which as the name suggests, accumulates as we continue to loop through the terms of the array. It accumulates based on the conditions we set for it within the function, which in this case is to increment by the value of the current element.

I hope that helped:)

Upvotes: 0

Related Questions