Write a pseudocode for finding the value of the largest element in a list of n numbers

Pseudocode and Flowchart for finding the largest element in an Array

[35188 views]

Array is a data structure consisting of a collection of homogenous data type or element (values or variables), each identified by at least one array index or key. An array is stored in such a manner that the position of each element can be found out from its index tuple by using a mathematical formula. The simplest data structure is a linear array, also known as one-dimensional array.

Arrays are among the most important data structures and are used in almost every program. They can be also used to implement many other data structures, such as linked-lists and stacks. The most important fact is that arrays are linear datatypes in which data is stored in sequence. In many internal and external storage devices, the memory is a one-dimensional array of words, whose indices are their addresses. We can access the elements if we know their indexes directly so, we can say that random access is possible in array.

Flowchart for finding the largest element in an Array :

Remove WaterMark from Above Flowchart

Algorithm to find the largest element in an Array :

Step 1: Start Step 2: Declare array a[n] and variable i, large Step 3: Read n from User and read all the elements of a[n] Step 4: Initialize Variable i=1 and large=a[0] Step 5: Repeat Until i<=n-1 5.1 if(a[i]>large), set large=a[i] 5.2 increment i=i+1 Step 6: Print "The largest element is": large Step 7: Stop

In the above algorithm,

1. We first take input the number of elements in the array from user and store it in variable n.
2. Then we declare a array a of size n and read it from the user.
3. We then declare two variables i and large.
4. Initialize i=1 and largest= a[0], the first element of the array a.
5. then we compare a[i] with large, if a[i] is greater we set large=a[i] We repeat the above step until (n-1) is greater than or equal to i.
6. At last, when we get out of the loop the value stored in the variable large is the largest element in an array.

15 Upvotes

6 Downvotes

Efficient Approach

• Firstly, program asks the user to input the values. So, user enter the size of array i.e. N and then enter the elements of array. Afterwards, program gives the output i.e. largest element in the entered array.
• We assign the first element value to the temp variable.
• Then we compare temp with all other elements inside a loop.
• If the temp is larger than all other elements,
• Then we return temp which store first element value as largest element.
• But if the element is larger than the temp,
• Then we store that element value into temp.
• This way temp will always store the largest value.
• Then we return temp.

Time complexity: O(N) where there are N elements in the array
Space complexity: O(1)

k largest(or smallest) elements in an array

Question: Write an efficient program for printing k largest elements in an array. Elements in an array can be in any order.
For example, if the given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30, and 23.

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Method 1 (Use Bubble k times)
Thanks to Shailendra for suggesting this approach.
1) Modify Bubble Sort to run the outer loop at most k times.
2) Print the last k elements of the array obtained in step 1.
Time Complexity: O(n*k)

Like Bubble sort, other sorting algorithms like Selection Sort can also be modified to get the k largest elements.

Method 2 (Use temporary array)
K largest elements from arr[0..n-1]

1) Store the first k elements in a temporary array temp[0..k-1].
2) Find the smallest element in temp[], let the smallest element be min.
3-a) For each element x in arr[k] to arr[n-1]. O(n-k)
If x is greater than the min then remove min from temp[] and insert x.
3-b)Then, determine the new min from temp[]. O(k)
4) Print final k elements of temp[]

Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + k*log(k))
Thanks to nesamani1822 for suggesting this method.

Method 3(Use Sorting)
1) Sort the elements in descending order in O(n*log(n))
2) Print the first k numbers of the sorted array O(k).

Following is the implementation of the above.

C++

// C++ code for k largest elements in an array #include <bits/stdc++.h> using namespace std; void kLargest(int arr[], int n, int k) { // Sort the given array arr in reverse // order. sort(arr, arr + n, greater<int>()); // Print the first kth largest elements for (int i = 0; i < k; i++) cout << arr[i] << " "; } // driver program int main() { int arr[] = { 1, 23, 12, 9, 30, 2, 50 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; kLargest(arr, n, k); } // This article is contributed by Chhavi

Java

// Java code for k largest elements in an array import java.util.Arrays; import java.util.Collections; import java.util.ArrayList; class GFG { public static void kLargest(Integer[] arr, int k) { // Sort the given array arr in reverse order // This method doesn't work with primitive data // types. So, instead of int, Integer type // array will be used Arrays.sort(arr, Collections.reverseOrder()); // Print the first kth largest elements for (int i = 0; i < k; i++) System.out.print(arr[i] + " "); } //This code is contributed by Niraj Dubey public static ArrayList<Integer> kLargest(int[] arr, int k) { //Convert using stream Integer[] obj_array = Arrays.stream( arr ).boxed().toArray( Integer[] :: new); Arrays.sort(obj_array, Collections.reverseOrder()); ArrayList<Integer> list = new ArrayList<>(k); for (int i = 0; i < k; i++) list.add(obj_array[i]); return list; } public static void main(String[] args) { Integer arr[] = new Integer[] { 1, 23, 12, 9, 30, 2, 50 }; int k = 3; kLargest(arr, k); //This code is contributed by Niraj Dubey //What if primitive datatype array is passed and wanted to return in ArrayList<Integer> int[] prim_array = { 1, 23, 12, 9, 30, 2, 50 }; System.out.print(kLargest(prim_array, k)); } } // This code is contributed by Kamal Rawal

Python

''' Python3 code for k largest elements in an array''' def kLargest(arr, k): # Sort the given array arr in reverse # order. arr.sort(reverse = True) # Print the first kth largest elements for i in range(k): print (arr[i], end =" ") # Driver program arr = [1, 23, 12, 9, 30, 2, 50] # n = len(arr) k = 3 kLargest(arr, k) # This code is contributed by shreyanshi_arun.

C#

// C# code for k largest elements in an array using System; class GFG { public static void kLargest(int[] arr, int k) { // Sort the given array arr in reverse order // This method doesn't work with primitive data // types. So, instead of int, Integer type // array will be used Array.Sort(arr); Array.Reverse(arr); // Print the first kth largest elements for (int i = 0; i < k; i++) Console.Write(arr[i] + " "); } // Driver code public static void Main(String[] args) { int[] arr = new int[] { 1, 23, 12, 9, 30, 2, 50 }; int k = 3; kLargest(arr, k); } } // This code contributed by Rajput-Ji

PHP

<?php // PHP code for k largest // elements in an array function kLargest(&$arr, $n, $k) { // Sort the given array arr // in reverse order. rsort($arr); // Print the first kth // largest elements for ($i = 0; $i < $k; $i++) echo $arr[$i] . " "; } // Driver Code $arr = array(1, 23, 12, 9, 30, 2, 50); $n = sizeof($arr); $k = 3; kLargest($arr, $n, $k); // This code is contributed // by ChitraNayal ?>

Javascript

<script> // JavaScript code for k largest // elements in an array function kLargest(arr, n, k) { // Sort the given array arr in reverse // order. arr.sort((a, b) => b - a); // Print the first kth largest elements for (let i = 0; i < k; i++) document.write(arr[i] + " "); } // driver program let arr = [ 1, 23, 12, 9, 30, 2, 50 ]; let n = arr.length; let k = 3; kLargest(arr, n, k); // This code is contributed by Manoj. </script>

Output 50 30 23

Time complexity: O(n*log(n))

Method 4 (Use Max Heap)
1) Build a Max Heap tree in O(n)
2) Use Extract Max k times to get k maximum elements from the Max Heap O(k*log(n))

Time complexity: O(n + k*log(n))

Method 5(Use Order Statistics)
1) Use an order statistic algorithm to find the kth largest element. Please see the topic selection in worst-case linear time O(n)
2) Use QuickSort Partition algorithm to partition around the kth largest number O(n).
3) Sort the k-1 elements (elements greater than the kth largest element) O(k*log(k)). This step is needed only if the sorted output is required.

Time complexity: O(n) if we don’t need the sorted output, otherwise O(n+k*log(k))
Thanks to Shilpi for suggesting the first two approaches.

Method 6 (Use Min Heap)
This method is mainly an optimization of method 1. Instead of using temp[] array, use Min Heap.
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k*log(k))
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
……a) If the element is greater than the root then make it root and call heapify for MH
……b) Else ignore it.
// The step 2 is O((n-k)*log(k))
3) Finally, MH has k largest elements, and the root of the MH is the kth largest element.
Time Complexity: O(k*log(k) + (n-k)*log(k)) without sorted output. If sorted output is needed then O(k*log(k) + (n-k)*log(k) + k*log(k)) so overall it is O(k*log(k) + (n-k)*log(k))

All of the above methods can also be used to find the kth largest (or smallest) element.

C++

#include <iostream> using namespace std; // Swap function to interchange // the value of variables x and y int swap(int& x, int& y) { int temp = x; x = y; y = temp; } // Min Heap Class // arr holds reference to an integer // array size indicate the number of // elements in Min Heap class MinHeap { int size; int* arr; public: // Constructor to initialize the size and arr MinHeap(int size, int input[]); // Min Heapify function, that assumes that // 2*i+1 and 2*i+2 are min heap and fix the // heap property for i. void heapify(int i); // Build the min heap, by calling heapify // for all non-leaf nodes. void buildHeap(); }; // Constructor to initialize data // members and creating mean heap MinHeap::MinHeap(int size, int input[]) { // Initializing arr and size this->size = size; this->arr = input; // Building the Min Heap buildHeap(); } // Min Heapify function, that assumes // 2*i+1 and 2*i+2 are min heap and // fix min heap property for i void MinHeap::heapify(int i) { // If Leaf Node, Simply return if (i >= size / 2) return; // variable to store the smallest element // index out of i, 2*i+1 and 2*i+2 int smallest; // Index of left node int left = 2 * i + 1; // Index of right node int right = 2 * i + 2; // Select minimum from left node and // current node i, and store the minimum // index in smallest variable smallest = arr[left] < arr[i] ? left : i; // If right child exist, compare and // update the smallest variable if (right < size) smallest = arr[right] < arr[smallest] ? right : smallest; // If Node i violates the min heap // property, swap current node i with // smallest to fix the min-heap property // and recursively call heapify for node smallest. if (smallest != i) { swap(arr[i], arr[smallest]); heapify(smallest); } } // Build Min Heap void MinHeap::buildHeap() { // Calling Heapify for all non leaf nodes for (int i = size / 2 - 1; i >= 0; i--) { heapify(i); } } void FirstKelements(int arr[],int size,int k){ // Creating Min Heap for given // array with only k elements MinHeap* m = new MinHeap(k, arr); // Loop For each element in array // after the kth element for (int i = k; i < size; i++) { // if current element is smaller // than minimum element, do nothing // and continue to next element if (arr[0] > arr[i]) continue; // Otherwise Change minimum element to // current element, and call heapify to // restore the heap property else { arr[0] = arr[i]; m->heapify(0); } } // Now min heap contains k maximum // elements, Iterate and print for (int i = 0; i < k; i++) { cout << arr[i] << " "; } } // Driver Program int main() { int arr[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 }; int size = sizeof(arr) / sizeof(arr[0]); // Size of Min Heap int k = 3; FirstKelements(arr,size,k); return 0; } // This code is contributed by Ankur Goel

Java

import java.io.*; import java.util.*; class GFG{ public static void FirstKelements(int arr[], int size, int k) { // Creating Min Heap for given // array with only k elements // Create min heap with priority queue PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for(int i = 0; i < k; i++) { minHeap.add(arr[i]); } // Loop For each element in array // after the kth element for(int i = k; i < size; i++) { // If current element is smaller // than minimum ((top element of // the minHeap) element, do nothing // and continue to next element if (minHeap.peek() > arr[i]) continue; // Otherwise Change minimum element // (top element of the minHeap) to // current element by polling out // the top element of the minHeap else { minHeap.poll(); minHeap.add(arr[i]); } } // Now min heap contains k maximum // elements, Iterate and print Iterator iterator = minHeap.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + " "); } } // Driver code public static void main (String[] args) { int arr[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 }; int size = arr.length; // Size of Min Heap int k = 3; FirstKelements(arr, size, k); } } // This code is contributed by Vansh Sethi

Python3

def FirstKelements(arr,size,k): # Creating Min Heap for given # array with only k elements # Create min heap with priority queue minHeap = [] for i in range(k): minHeap.append(arr[i]) # Loop For each element in array # after the kth element for i in range(k, size): minHeap.sort() # If current element is smaller # than minimum ((top element of # the minHeap) element, do nothing # and continue to next element if (minHeap[0] > arr[i]): continue # Otherwise Change minimum element # (top element of the minHeap) to # current element by polling out # the top element of the minHeap else: minHeap.pop(0) minHeap.append(arr[i]) # Now min heap contains k maximum # elements, Iterate and print for i in minHeap: print(i, end = " ") # Driver code arr=[11, 3, 2, 1, 15, 5, 4,45, 88, 96, 50, 45] size = len(arr) # Size of Min Heap k=3 FirstKelements(arr, size, k) # This code is contributed by avanitrachhadiya2155

C#

using System; using System.Collections.Generic; public class GFG { public static void FirstKelements(int []arr, int size, int k) { // Creating Min Heap for given // array with only k elements // Create min heap with priority queue List<int> minHeap = new List<int>(); for(int i = 0; i < k; i++) { minHeap.Add(arr[i]); } // Loop For each element in array // after the kth element for(int i = k; i < size; i++) { minHeap.Sort(); // If current element is smaller // than minimum ((top element of // the minHeap) element, do nothing // and continue to next element if (minHeap[0] > arr[i]) continue; // Otherwise Change minimum element // (top element of the minHeap) to // current element by polling out // the top element of the minHeap else { minHeap.RemoveAt(0); minHeap.Add(arr[i]); } } // Now min heap contains k maximum // elements, Iterate and print foreach (int i in minHeap) { Console.Write(i + " "); } } // Driver code public static void Main(String[] args) { int []arr = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 }; int size = arr.Length; // Size of Min Heap int k = 3; FirstKelements(arr, size, k); } } // This code is contributed by aashish2995.

Javascript

<script> function FirstKelements(arr , size , k) { // Creating Min Heap for given // array with only k elements // Create min heap with priority queue var minHeap = []; for (var i = 0; i < k; i++) { minHeap.push(arr[i]); } // Loop For each element in array // after the kth element for (var i = k; i < size; i++) { minHeap.sort((a,b)=>a-b); // If current element is smaller // than minimum ((top element of // the minHeap) element, do nothing // and continue to next element if (minHeap[minHeap.length-3] > arr[i]) continue; // Otherwise Change minimum element // (top element of the minHeap) to // current element by polling out // the top element of the minHeap else { minHeap.reverse(); minHeap.pop(); minHeap.reverse(); minHeap.push(arr[i]); } } // Now min heap contains k maximum // elements, Iterate and print for (var iterator of minHeap) { document.write(iterator + " "); } } // Driver code var arr = [11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45]; var size = arr.length; // Size of Min Heap var k = 3; FirstKelements(arr, size, k); // This code is contributed by gauravrajput1 </script>

Output 50 88 96

Method 7(Using Quick Sort partitioning algorithm):

1. Choose a pivot number.
2. if K is lesser than the pivot_Index then repeat the step.
3. if K == pivot_Index : Print the array (low to pivot to get K-smallest elements and (n-pivot_Index) to n for K-largest elements)
4. if K > pivot_Index : Repeat the steps for right part.

We can improve on the standard quicksort algorithm by using the random() function. Instead of using the pivot element as the last element, we can randomly choose the pivot element. The worst-case time complexity of this version is O(n2) and the average time complexity is O(n).

Following is the implementation of the above algorithm:

C++

#include <bits/stdc++.h> using namespace std; //picks up last element between start and end int findPivot(int a[], int start, int end) { // Selecting the pivot element int pivot = a[end]; // Initially partition-index will be // at starting int pIndex = start; for (int i = start; i < end; i++) { // If an element is lesser than pivot, swap it. if (a[i] <= pivot) { swap(a[i], a[pIndex]); // Incrementing pIndex for further // swapping. pIndex++; } } // Lastly swapping or the // correct position of pivot swap(a[pIndex], a[end]); return pIndex; } //THIS PART OF CODE IS CONTRIBUTED BY - rjrachit //Picks up random pivot element between start and end int findRandomPivot(int arr[], int start, int end) { int n = end - start + 1; // Selecting the random pivot index int pivotInd = random()%n; swap(arr[end],arr[start+pivotInd]); int pivot = arr[end]; //initialising pivoting point to start index pivotInd = start; for (int i = start; i < end; i++) { // If an element is lesser than pivot, swap it. if (arr[i] <= pivot) { swap(arr[i], arr[pivotInd]); // Incrementing pivotIndex for further // swapping. pivotInd++; } } // Lastly swapping or the // correct position of pivot swap(arr[pivotInd], arr[end]); return pivotInd; } //THIS PART OF CODE IS CONTRIBUTED BY - rjrachit void SmallestLargest(int a[], int low, int high, int k, int n) { if (low == high) return; else { int pivotIndex = findRandomPivot(a, low, high); if (k == pivotIndex) { cout << k << " smallest elements are : "; for (int i = 0; i < pivotIndex; i++) cout << a[i] << " "; cout << endl; cout << k << " largest elements are : "; for (int i = (n - pivotIndex); i < n; i++) cout << a[i] << " "; } else if (k < pivotIndex) SmallestLargest(a, low, pivotIndex - 1, k, n); else if (k > pivotIndex) SmallestLargest(a, pivotIndex + 1, high, k, n); } } // Driver Code int main() { int a[] = { 11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45 }; int n = sizeof(a) / sizeof(a[0]); int low = 0; int high = n - 1; // Lets assume k is 3 int k = 4; // Function Call SmallestLargest(a, low, high, k, n); return 0; }

Output 3 smallest elements are : 3 2 1 3 largest elements are : 96 50 88

Please write comments if you find any of the above explanations/algorithms incorrect, or find better ways to solve the same problem.
References:
http://en.wikipedia.org/wiki/Selection_algorithm

Article Tags :

Arrays

Heap

Searching

Sorting

Amazon

Microsoft

Order-Statistics

Samsung

Walmart

Practice Tags :

Amazon

Microsoft

Samsung

Walmart

Arrays

Searching

Sorting

Heap

Find the minimum and maximum value in an array

Difficulty: Medium

Asked in: Facebook

Understanding the Problem

Problem Description: Given an array A[] of size n, you need to find the maximum and minimum element present in the array. Your algorithm should make the minimum number of comparisons.

For Example:

Input: A[] = { 4, 2, 0, 8, 20, 9, 2}

Output: Maximum: 20, Minimum: 0

Input: A[] = {-8, -3, -10, -32, -1}

Output: Maximum: -1, Minimum: -32

Possible follow-up questions to ask the interviewer :-

1. Are the array elements necessarily positive? (Ans: No, they can be positive, negative, or zero)
2. Are the array element sorted ? (Ans: No, they can be in any order)
3. Can the array contain duplicates? (Ans: Sure, that's a possibility.)

Problem Note:- The interviewer would not judge your algorithm for this question based on the time complexity as all solution has the time complexity of O(n). The bottleneck parameter in this problem is the number of comparisons that your algorithm requires to determine the maximum and the minimum element. You need to decrease the number of comparisons as much as you can.

Solutions

1. Searching linearly: Increment the loop by 1
2. Divide and Conquer: Tournament Method
3. Comparison in pairs: Increment the loop by 2

1. Searching linearly: Increment the loop by 1

We initialize both minimum and maximum element to the first element and then traverse the array, comparing each element and update minimum and maximum whenever necessary.

Pseudo-Code

Complexity Analysis

At every step of the loop, we are doing 2 comparisons in the worst case. Total no. of comparisons (in worst case) = 2*(n-1) = 2n - 2

Time complexity = O(n), Space complexity = O(1)

In the best case, a total of n-1 comparisons have been made. (How?)

Critical ideas to think!

• We have initialized maximum and minimum with the first element of the array - why?
• What would be the best case and worst case input?
• How can we decrease the number of comparisons made here?

2. Divide and Conquer : Tournament Method

Another way to do this could be by following the divide and conquer strategy. Just like the merge sort, we could divide the array into two equal parts and recursively find the maximum and minimum of those parts. After this, compare the maximum and minimum of those parts to get the maximum and minimum of the whole array.

Solution Steps

1. Write a recursive function accepting the array and its start and end index as parameters
2. The base cases will be

• If array size is 1, return the element as both max and min
• If array size is 2, compare the two elements and return maximum and minimum

3. The recursive part is

• Recursively calculate and store the maximum and minimum for left and right parts
• Determine the maximum and minimum among these by 2 comparisons

4. Return max and min.

Pseudo Code

Complexity Analysis

For counting the number of comparisons, since this is a recursive function, let us define the recurrence relation :

Time complexity = O(n) and space complexity = O(logn) (For recursion call stack)

If n is a power of 2, the algorithm needs exactly 3n/2–2 comparisons to find min and max. If it's not a power of 2, it will take a few more(not significant).

Critical ideas to think!

• How do we analyze the recursion by the master's theorem and recursion tree method?
• How is the space complexity derived to be O(logn)?
• Why there are 2 base cases? What if we remove the base case with array size 2?
• Why prefer mid = start + (end - start)/2 over (start + end)/2 when calculating middle of the array ?
• Can the number of comparisons be decreased further?

3. Comparison in Pairs : Increment the loop by 2

In this approach, we pick array elements in pairs and update the min and max. If the array size is odd, we initialize the first element as both min and max, and if it's even, we compare the first two elements and initialize min and max accordingly.

Solution Steps

1. Create max and min variables.
2. Check for the size of the array

• If odd, initialize min and max to the first element
• If even, compare the elements and set min to the smaller value and max to the bigger value

3. Traverse the array in pairs

4. For each pair, compare the two elements and then

• Compare the bigger element with max, update max if required.
• Compare the smaller element with min, update min if required.

5. Return max and min.

Pseudo Code

Complexity Analysis

Time Complexity is O(n) and Space Complexity is O(1).

For each pair, there are a total of three comparisons, first among the elements of the pair and the other two with min and max.

Total number of comparisons:-

• If n is odd, 3 * (n-1) / 2
• If n is even, 1 + 3*(n-2)/2 = 3n/2-2

Critical ideas to think!

• Why min and max are initialized differently for even and odd sized arrays?
• Why incrementing the loop by 2 help to reduce the total number of comparsion ?
• Is there any other way to solve this problem? Think.
• In which case, the number of comparisons by method 2 and 3 is equal?

Comparison of different solutions

Suggested Problems to solve

• Find the smallest and second smallest element in the array using minimum number of comparsions
• Find the minimum element in a sorted and rotated array
• Find Kth largest element in an array
• Find K largest element in an array
• Find the middle element among three numbers
• Find median of k sorted arrays

Please write comments if you find any error or bug. Happy Coding! Enjoy Algorithms!

AfterAcademy Data Structure And Algorithms Online Course - Admissions Open