Array - 1D
List
Tree
Stack and Queue
Algorithm
Sorting
Array
- Same Data Type
- Cosecutive in memory
- Access using index
- Index value is integer
- Fixed Size
- Access time is faster than list.
1 Dimensional Array/ Linear Array ( Index starts from 1)
Integer Num_array 1 2 3 4 5 6
Num_array[1] = 1
Num_array[2] = 2
Num_array[3] = 3
Num_array[4] = 4
Num_array[5] = 5
Num_array[6] = 6
Print (Num_array[6]) //10
Using Looping
For I from 1 to 6 by 1
Print (“Enter a value”)
Integer value=input()
Num_array[i] = value
End For
Shift all elements of an array to right for 1 position.
Integer Num_array 1 2 3 4 5 6
6 1 2 3 4 5
Integer temp=6
Num_array[2]=num_array[1]
6 1 2 3 4 5 Temp= 6
Integer temp=Num_array [len(Num_array)]
I=5
Num_array[6]=Num_array[5]
I=4
Num_array[5]=Num_array[4]
I=3
Num_array[4]=Num_array[3]
I=2
Num_array[3]=Num_array[2]
I=1
Num_array[2]=Num_array[1]
Index starts 1.
Temp= 6
I= 5
Num_array[6]=Num_array[5]
I= 4
Num_array[5]=Num_array[4]
I= 3
Num_array[4]=Num_array[3]
I= 2
Num_array[3]=Num_array[2]
I= 1
Num_array[2]=Num_array[1]
I= 0
Num_array[1]=Num_array[0]
Temp= 6
I=5
I>= 1 => Numarray[6]=Numarray[5]
I=4
I>= 1 => Numarray[5]=Numarray[4]
I=3
I>= 1 => Numarray[4]=Numarray[3]
I=2
I>= 1 => Numarray[3]=Numarray[2]
I=1
I>= 1 => Numarray[2]=Numarray[1]
Measure Time Complexity and Space Complexity.
Time Complexity = O( n ) =>Big O Notation
Space Complexity = O (1)
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different
day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit,
return 0.
Example
Input: prices =[ 7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price =1) and sell on day 5 (price = 6), profit = 6-1 = 5
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Price [ 7,1,5,3,6,4]
D1-> D2= 0, D3= 0, D4=0, D5=0,D6=0
D2-> D3= 4,D4 = 2,D5= 5,D6 = 3
D3-> D4=0,D5 =1,D6 =0
D4-> D5= 3,D6 = 1
D5 ->D6 =0
Integer max=0
Buy=0
Sell=0
For ( i from 1 to 5 by 1) {
For (j from i+1 to 6 by 1){
If ( price[j] > price [i] {
profit= price[j]- price[i]
If (max < profit) {
max= profit;
Buy= i
Sell= j
}
}
}
}
return Buy, Sell,max
3. Rotate array by K elements
Problem Statement: Given an array of integers, rotating array of elements by k elements either left or
right. Array index starts at 1.
Example 1:
Input: N = 7, array[] = {1,2,3,4,5,6,7} , k=2 , right
Output: 6 7 1 2 3 4 5
Explanation: array is rotated to right by 2 position .
Integer k=2
Integer temp[]= [len(array)] //length= 7
Integer i=len(array); 1 2 1 2 3 4 5
For ( integer x=k; x >= 1; x--){
6 7 1 2 3 4 5
Temp[x] = array[i]
i--;
}
For ( integer z from len(array)-k to 1 by z-- ){
z= 7- 2= 5 => temp[5+2]=Array[5]
z= 4 => temp[4+2]=Array[4]
z= 3 => temp[3+2]=Array[3]
z= 2 => temp[2+2]=Array[2]
z= 2 => temp[1+2]=Array[1]
temp[z+k]=Array[z]
}
Example 2:
Input: N = 6, array[] = {3,7,8,9,10,11} , k=3 , left
Output: 9 10 11 3 7 8
Explanation: Array is rotated to left by 3 position.
Revised Array
Integer num_array[]={1,2,3,4,5,6,7} // length= 4 1 2 3 4 5 6 7
Integer num2_array[]= [len(num_array)] 7 6 5 4 3 2 1
//Copy elements from num_array into num2_array
num2_array[1] = num_array[1]
num2_array[2] = num_array[2]
num2_array[3] = num_array[3]
num2_array[4] = num_array[4]
num2_array[5] = num_array[5]
num2_array[6] = num_array[6]
num2_array[7] = num_array[7]
Alternative Way using looping
// Copy data from num_array into num2_array
For ( integer i from 1 to 6 by 1) {
num2_array[ i ] = num_array[i ]
}
// Reverse data from num_array into num2_array
For ( integer i from 0 to 6 by 1) {
num2_array[ len(num2_array) - i ] = num_array[i +1 ]
}
4. Write a pseudo code to print the count of 0 (zero ) elements from an array. Array index starts from 1.
Input: input [] ={ 2,0,8,0,3,1,0,0}
Output: 4
Integer count=0
For (integer I from 1 to len( input ) by 1) {
If ( input[I] = 0 )
count= count+1
}
Print (count)
Assignment
5. Modify the above code, to print the count of each elements from an array. Array index starts from 1.
Input: input [] ={ 2,0,8,0,3,1,2,0,1}
Output: element 2 = 2
element 0 = 3
element 8 = 1
element 3 = 1
6. Given an array of integers arr, return true if the number of occurrences of each value in the array is
unique or false otherwise.
Example 1:
Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number
of occurrences.
Example 2:
Input: arr = [1,2]
Output: false
Example 3:
Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true
7. Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the
non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
8. Rotate array by k positions to right.
9. Rotate array by k positions to left
Reverse the entire array.
- Reverse the first k elements and the remaining elements separately.
