CODEWITHSUNDEEP
kotlinsizefenwick-treemutablelistbinary-indexed-tree
Kushagra
Kushagra

Reputation: 41

how to increase the size limit of a mutable list in kotlin?

I was attempting to solve the multiset question (https://codeforces.com/contest/1354/problem/D) on codeforces using Fenwick Tree Data structure. I passed the sample test cases but got the memory limit error after submitting, the testcase is mentioned below. (Basically the testcase is:

1000000 1000000

1.............1 //10^6 times

-1...........-1 //10^6 times).

I tried similar testcase in my IDE and got the below mentioned error. (Similar to above, the testcase I provided is:

1000000 1

1.............1 //10^6 times

-1

)

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 524289 out of bounds for length 524289 at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64) at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70) at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248) at java.base/java.util.Objects.checkIndex(Objects.java:373) at java.base/java.util.ArrayList.get(ArrayList.java:426) at MultisetKt.main(multiset.kt:47) at MultisetKt.main(multiset.kt)

Here is my code:

private fun readInt() = readLine()!!.split(" ").map { it.toInt() }

fun main() {
    var (n, q) = readInt()
    var list = readInt() //modify the list to store it from index 1
    var finalList = listOf(0) + list
    val query = readInt()
    var bit  = MutableList(n+1){0}

    fun update(i:Int, value:Int) {
        var index = i
        while(index < n){
            bit.set (index , bit[index] + value)
            index += (index and -index)
        }
    }
    fun rangefunc(i:Int): Int {
        var su = 0
        var index = i
        while(index > 0){
            su += bit[index]
            index -= (index and -index)
        }
        return su
    }
    fun find(x:Int):Int {
        var l = 1
        var r = n
        var ans = n
        var mid = 0
        while (l <= r) {
            mid = (l + r) / 2
            if (rangefunc(mid) >= x) {
                ans = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return ans
    }
    for (i in 1..n) {
        update(finalList[i], 1)
    }
    for (j in 0..q - 1) {
        if (query[j] > 0) {
            update(query[j], 1)
        } else {
            update(find(-query[j]), -1)
        }
    }
    if(rangefunc(n) == 0){
        println(0)
    }else{
        println(find(1))
    }
}

I believe this is because the BITlist is not able to store 10^6 elements but not sure. Please let me know what changes should I make in my code also any additional advice on how to deal with such cases in the future.

Thank you in advance :)

Upvotes: 0

Views: 2920

Answers (1)

Tenfour04
Tenfour04

Reputation: 93779

An ArrayList can store over 2 billion items (2 * 10^9). That is not your issue. ArrayIndexOutOfBoundsException is for trying to access an index of an ArrayList that is less than zero or greater than or equal to its size. In other words, an index that it doesn't yet contain.

There's more code there than I have time to debug. But I would start at the line that the stack trace points to and see how it's possible for you to attempt to call bit[index] with an index that equals the size of the ArrayList.

To answer your literal question, you can use LinkedList explicitly as your type of MutableList to avoid the size restriction, but it is heavier and it is slower when accessing elements by index.

Upvotes: 3

Related Questions