CODEWITHSUNDEEP
scala
Mansur Ashraf
Mansur Ashraf

Reputation: 1357

Scala: Find max element of a sub list

I need to write a function that takes a List[Int], start index and end index and returns the max element within that range. I have a working recursive solution but I was wondering if its possible to do it using a built-in function in the Scala collection library.

Additional criteria are:

1) O(N) run time 2) No intermediate structure creation 3) No mutable data structures

def sum(input:List[Int],startIndex:Int,endIndex:Int): Int = ???

Upvotes: 1

Views: 321

Answers (2)

wingedsubmariner
wingedsubmariner

Reputation: 13667

This is easily possible with Scala's views:

def subListMax[A](list: List[A], start: Int, end: Int)(implicit cmp: Ordering[A]): A =
  list.view(start, end).max

view does not create an intermediate data structure, it only provides an interface into a slice of the original one. See the Views chapter in the documentation for the Scala collections library.

Upvotes: 2

Kigyo
Kigyo

Reputation: 5768

I think it is not possible with your criteria.

There is no higher order function known to me, which works on a sublist of a list. Many just create intermediate collections.

This would be a simple O(n) solution, but it creates an intermediate structure.

input.slice(startIndex, endIndex + 1).max

There are of course also functions, which traverse a collection and yield a value. Examples are reduce and foldLeft. The problem is that they traverse the whole collection and you can't set a start or end.

You could iterate from startIndex to endIndex and use foldLeft on that to get a value via indexing. An example would be:

(startIndex to endIndex).foldLeft(Integer.MIN_VALUE)((curmax, i) => input(i).max(curmax))

Here we only have an iterator, which basically behaves like a for-loop and produces no heavy intermediate collections. However iterating from startIndex to endIndex is O(n) and on each iteration we have an indexing operation (input(i)) that is also generally O(n) on List. So in the end, sum would not be O(n).

This is of course only my experience with scala and maybe I am misguided.

Ah and on your 3): I'm not sure what you mean by that. Using mutable state inside the function should not be a problem at all, since it only exists to compute your result and then disappear.

Upvotes: 0

Related Questions