Lesson

4.5find the smallest no in the array

Finding the Smallest Element in an Array

Problem Statement

Given an array of integers, find the smallest (minimum) element in the array.

Example

Approaches

Brute Force Approach

Idea: Iterate through the array and keep track of the minimum element found so far.
Steps:
1. Initialize a variable minElement with the first element of the array.
2. Iterate through the array starting from the second element.
3. For each element, compare it with minElement.
4. If the element is smaller than minElement, update minElement.
5. Return minElement at the end.
Time Complexity: O(n) - We need to traverse all elements in the array.
Space Complexity: O(1) - No extra space is required, just a variable to store the minimum.
Example:

Test Cases:
1. Input: [1, 2, 3, 4, 5] | Output: 1
2. Input: [5, 4, 3, 2, 1] | Output: 1
3. Input: [-3, -5, -7, -2, -8, -1, -4] | Output: -8
4. Input: [100] | Output: 100
5. Input: [] | Output: undefined (Empty Array)

Using JavaScript's Built-in Function

Idea: Use JavaScript's built-in Math.min() function along with the spread operator to find the minimum element.
Steps:
1. Simply return Math.min(...array).
Time Complexity: O(n) - Internally, Math.min() also traverses the entire array.
Space Complexity: O(1) - No extra space is required.
Example:

Test Cases:
1. Input: [1, 2, 3, 4, 5] | Output: 1
2. Input: [5, 4, 3, 2, 1] | Output: 1
3. Input: [-3, -5, -7, -2, -8, -1, -4] | Output: -8
4. Input: [100] | Output: 100
5. Input: [] | Output: Infinity (Empty Array)

Divide and Conquer Approach (Recursive) (Optional - for people who understand recursion)

Idea: Recursively divide the array into two halves and find the minimum in each half. Compare the two minimums to get the overall minimum.
Steps:
1. Base case: If the array has one element, return that element.
2. Recursively find the minimum in the left half and the right half.
3. Return the smaller of the two.
Time Complexity: O(n) - Every element is compared once.
Space Complexity: O(log n) - Due to recursive calls.
Example:

Test Cases:
1. Input: [1, 2, 3, 4, 5] | Output: 1
2. Input: [5, 4, 3, 2, 1] | Output: 1
3. Input: [-3, -5, -7, -2, -8, -1, -4] | Output: -8
4. Input: [100] | Output: 100
5. Input: [] | Output: undefined (Empty Array)

Conclusion

All methods discussed have a time complexity of O(n), but the space complexity varies. The brute force and built-in methods are more straightforward and efficient in terms of space, while the recursive method uses more space due to the recursive stack.

Previous Next