Problem Solving

Problem Statement

You are given an array of integers. Your task is to find the second largest element in the array. The array may contain duplicate elements.

Example:

      Input: arr = [12, 35, 1, 10, 34, 1]
      Output: 34
      Explanation: The largest element is 35, the second largest is 34.
        

Example 2:

      Input: arr = [5, 5, 5, 2]
      Output: 2
      Explanation: The largest element is 5 (repeated), second largest is 2.
        

Solution Approach

1. Initialize two variables: largest and secondLargest with Int.MIN_VALUE.
2. Traverse the array once.
3. For each element:
   • If element is greater than largest, update secondLargest to largest and then update largest to the element.
   • Else if element is greater than secondLargest and not equal to largest, update secondLargest.
4. After traversal, secondLargest contains the second largest element.

Kotlin Solution

      fun findSecondLargest(arr: Array): Int {
          var largest = Int.MIN_VALUE
          var secondLargest = Int.MIN_VALUE

          arr.forEach { num ->
              if (num > largest) {
                  secondLargest = largest
                  largest = num
              } else if (num > secondLargest && num != largest) {
                  secondLargest = num
              }
          }

          return secondLargest
      }

      fun main() {
          val arr = arrayOf(12, 35, 1, 10, 34, 1)
          val secondLargest = findSecondLargest(arr)
          println("Second largest element is: $secondLargest") // Output: 34
      }
        

Step-by-Step Example

For arr = [12, 35, 1, 10, 34, 1]:

1. Start: largest = MIN_VALUE, secondLargest = MIN_VALUE
2. 12 → largest = 12, secondLargest = MIN_VALUE
3. 35 → largest = 35, secondLargest = 12
4. 1 → largest = 35, secondLargest = 12
5. 10 → largest = 35, secondLargest = 12
6. 34 → largest = 35, secondLargest = 34
7. 1 → largest = 35, secondLargest = 34

Result: secondLargest = 34

Explanation

• This approach keeps track of the two largest numbers in a single pass.
• No extra array or filtering is needed.
• Handles duplicates correctly by checking num != largest.

Complexity Analysis

• Time Complexity: O(N) — Only one traversal of the array is needed.
• Space Complexity: O(1) — Only two variables are used.

Edge Cases

• If the array has all elements the same, the second largest might not exist — you may return a special value or handle separately.
• If the array has less than 2 distinct elements, handle accordingly.