CPSC 131 –
Intro. to Computer Programming II
Dongsheng Che
Department of Computer Science
East Stroudsburg University
Arrays (Chapter 6)
Dongsheng Che
Department of Computer Science
East Stroudsburg University
Array Basics
Array declaration and Initialization
Array Elements and indices
More Arrays
Array Variable and Reference
Declares an array variable, myList,
Creates an array of 10 elements of double type and assigns its
reference to myList
double[] myList = new double[10];
Program Demos
• Array Basics
• Array Reference
Array Reference and Elements
Reference Copy
Enhanced For Loop
Syntax for the enhanced for loop
Syntax 6.2: The Enhanced for loop
Use the enhanced “for” loop when:
➢ You need to access every element in the array
➢ You do not need to change any elements of the array
An Example: Enhanced For Loop
Hands-on Exercise: (Array_Enhanced_Loop)
Complete the code below:
➢ Declare a string array to store a list of courses in your array
➢ Use an enhanced for loop to print each course
Array Algorithms
• Maximum/Minimum
• Removing an element
• Inserting an element
Maximum and Minimum
Enhanced for to double largest = values[0];
find maximum for (double element : values) {
if element > largest)
largest = element;
}
Enhanced for to double smallest = values[0];
find minimum for (double element : values) {
if element < smallest)
smallest = element;
}
Inserting an Element
if (currentSize < [Link]) {
currentSize++;
for (int i = currentSize - 1; i > pos; i--) {
values[i] = values[i - 1]; // move down
}
values[pos] = newElement; // fill hole
}
Remove an element
for (int i = pos; i < currentSize - 1; i++) {
values[i] = values[i + 1];
}
currentSize--;
More Array Algorithms
Program Demos
• Array Algorithms
Array Methods
Method Using Array
Actual Parameter(s) or Argument(s)
Formal Parameter(s)
Pass-by Reference Mechanism
reference copy value copy
Program Demos
• Array Methods
Hands-on Exercise: Array_Method_Highest
Complete the method findHighest in class Array_Method_Highest
Array Interview Questions
P1: Find minimum and maximum
Given an array A of size N of integers. Your task is to find the minimum and
maximum elements in the array.
Example 1:
Input: N = 6 A[] = {3, 2, 1, 56, 10000, 167}
Output: min = 1, max = 10000
Example 2:
Input: N = 5 A[] = {1, 345, 234, 21, 56789}
Output: min = 1, max = 56789
P2: Reverse a string
You are given a string s. You need to reverse the string.
Example 1:
Input: s = Java
Output: avaJ
Example 2:
Input: s = for
Output: rof
P3: Sort the array
Given a random set of numbers, Print them in sorted order.
Example 1:
Input: N = 4 arr[] = {1, 5, 3, 2}
Output: {1, 2, 3, 5}
Explanation: After sorting array will be like {1, 2, 3, 5}.
Example 2:
Input: N = 2 arr[] = {3, 1}
Output: {1, 3}
Explanation: After sorting array will be like {3, 1}.
P4: Sort an array of 0s, 1s and 2s
Given an array of size N containing only 0s, 1s, and 2s; sort the array in
ascending order.
Example 1:
Input: N = 5 arr[]= {0 2 1 2 0}
Output: 0 0 1 2 2
Explanation: 0s 1s and 2s are segregated into ascending order.
Example 2:
Input: N = 3 arr[] = {0 1 0}
Output: 0 0 1
Explanation: 0s 1s and 2s are segregated into ascending order.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
P5: Kth smallest element
Given an array arr[] and an integer K where K is smaller than size of array,
the task is to find the Kth smallest element in the given array. It is given
that all array elements are distinct.
Example 1:
Input: N = 6 arr[] = 7 10 4 3 20 15 K = 3
Output : 7
Explanation : 3rd smallest element in the given array is 7.
Example 2:
Input: N = 5 arr[] = 7 10 4 20 15 K = 4
Output : 15
Explanation : 4th smallest element in the given array is 15.
P6: Find the Frequency
Given a vector of N positive integers and an integer X. The task is to find
the frequency of X in vector.
Example 1:
Input: N = 5 vector = {1, 1, 1, 1, 1} X = 1
Output: 5
Explanation: Frequency of 1 is 5.
P7: Peak element
A peak element in an array is the one that is not smaller than its neighbors.
Given an array arr[] of size N, find the index of any one of its peak elements.
Example 1:
Input: N = 3 arr[] = {1,2,3}
Output: 2
Explanation: index 2 is 3. It is the peak element as it is greater than its neighbor 2.
Example 2:
Input: N = 2 arr[] = {3,4,2}
Output: 1
Explanation: 4 (at index 1) is the peak element as it is greater than its neighbors
element 3 (left) and element 2 (right).
Basic Idea
The idea here is to traverse an array and check if current
number is greater than the next number (arr[i] > arr[i+1]). If
it is then it’s a peak element.
P8: Subarray with given sum
Given an unsorted array A of size N that contains only non-negative
integers, find a continuous sub-array which adds to a given number S.
Example 1:
Input: N = 5, S = 12 A[] = {1,2,3,7,5}
Output: 2 4
Explanation: The sum of elements from 2nd position to 4th position is
12.
Example 2:
Input: N = 10, S = 15 A[] = {1,2,3,4,5,6,7,8,9,10}
Output: 1 5
Explanation: The sum of elements from 1st position to 5th position is 15.
Brute force approach
[Link] outer loop from range[0 to n-1]. Loop
variable is start.
[Link] inner loop from range[start+1,n]. Loop
variable is end.
[Link] a loop nested into the above loop from
range[start,end-1] and calculate the sum in this
range.
[Link] sum equals to given k, then increase the
value of count.
P9: Move negative elements to end
Given an unsorted array arr[] of size N having both negative and positive
integers. The task is place all negative element at the end of array.
Example 1:
Input : N = 8 arr[] = {1, -1, 3, 2, -7, -5, 11, 6 }
Output : 1 3 2 11 6 -1 -7 -5
Example 2:
Input : N=8 arr[] = {-5, 7, -3, -4, 9, 10, -1, 11}
Output : 7 9 10 11 -5 -3 -4 -1
Basic Idea
temp
temp
Hands-on Exercise: Array_MoveNegToEnd
Complete the method MoveNegToEnd in class Array_MoveNegToEnd
P10: Union of two arrays
Given two arrays a[] and b[] of size n and m respectively. The task is to
find union between these two arrays and return number of union set.
Union of the two arrays can be defined as the set containing distinct
elements from both the arrays. If there are repetitions, then only one
occurrence of element should be printed in the union.
Example 1:
Input: n=5 m=3 a= [1 2 3 4 5] b=[1 2 3]
Output: 5
Explanation: 1, 2, 3, 4 and 5 are the elements which comes in the union
set of both arrays. So count is 5.
Example 2:
Input: n=6 m=2 a=[85 25 1 32 54 6] b=[85 2]
Output: 7
Explanation: 85, 25, 1, 32, 54, 6, and 2 are the elements which comes in
the union set of both arrays. So count is 7.
Merge sort Idea
Multi Dimension Array
Syntax 6.3: 2D Array Declaration
The name of the array continues to be a reference to the
contents of the array
➢ Use new or fully initialize the array
2D Array Elements
2D Array Declaration & Initialization
2D Array References
Program Demos
• Multi Dimensional Arrays
Hands-on Exercise: Array_MultiplicationTable
Complete statements to fill the multiplication table in each cell
ArrayList
ArrayList Methods
Syntax 6.4: Array Lists
ArrayList provides many useful methods:
➢ add: add an element
➢ get: return an element
➢ remove: delete an element
▪ set: change an element
▪ size: current length
ArrayList Example
Array and ArrayList
Program Demos
• ArrayLists