Data structure: Array
Array is a container which can hold a fix number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms. Following are the important terms to understand the concept of Array.
- Element − Each item stored in an array is called an element.
- Index − Each location of an element in an array has a numerical index, which is used to identify the element.
Example:-
Why do we need arrays?
We can use normal variables (v1, v2, v3, ..) when we have a small number of objects, but if we want to store a large number of instances, it becomes difficult to manage them with normal variables. The idea of an array is to represent many instances in one variable.
http://quiz.geeksforgeeks.org/c-language-2/arrays-pointers/
We can use normal variables (v1, v2, v3, ..) when we have a small number of objects, but if we want to store a large number of instances, it becomes difficult to manage them with normal variables. The idea of an array is to represent many instances in one variable.
http://quiz.geeksforgeeks.org/c-language-2/arrays-pointers/
Array declaration in C/C++:
There are various ways in which we can declare an array. It can be done by specifying its type and size, by initializing it or both.
Array Declaration:-
1. Array declaration by specifying size
2. Array declaration by initializing elements
3. Array declaration by specifying size and initializing elements
To clear your concepts you can follow these steps...
Step 1: Visit this article to clear your basic theory
Step 2: Visit this article to deep-dive into Queue
Some additional see-through contents...
1. Introduction to Arrays
Step 1: Visit this article to clear your basic theory
Step 2: Visit this article to deep-dive into Queue
Some additional see-through contents...
1. Introduction to Arrays
2. Array Operations - Traversal | Insertion
3. Array Operations - Deletion
4. Pointers and Arrays
5. Introduction to Two Dimensional (2D) Arrays
Problem Set: Level Basic
2. C program to find sum of array elements (Solution)
Problem Set: Level Intermediate
1. Longest Span with same Sum in two Binary arrays
Given two binary arrays arr1[] and arr2[] of same size n. Find length of the longest common span (i, j) where j >= i such that arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] + arr2[i+1] + …. + arr2[j].
Expected time complexity is Θ(n). (Solution)
2. Union and Intersection of two sorted arrays
Given two sorted arrays, find their union and intersection. (Solution)
Given two sorted arrays, find their union and intersection. (Solution)
Example:
Input : arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Output : Union : {1, 2, 3, 4, 5, 6, 7}
Intersection : {3, 5}
Input : arr1[] = {2, 5, 6}
arr2[] = {4, 6, 8, 10}
Output : Union : {2, 4, 5, 6, 8, 10}
Intersection : {6}
3. Find the minimum distance between two numbers
Given an unsorted array arr[] and two numbers x and y, find the minimum distance between x and y in arr[]. The array might also contain duplicates. You may assume that both x and y are different and present in arr[]. (Solution)
Examples:
Input: arr[] = {1, 2}, x = 1, y = 2
Output: Minimum distance between 1 and 2 is 1.
Input: arr[] = {3, 4, 5}, x = 3, y = 5
Output: Minimum distance between 3 and 5 is 2.
Input: arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}, x = 3, y = 6
Output: Minimum distance between 3 and 6 is 4.
Input: arr[] = {2, 5, 3, 5, 4, 4, 2, 3}, x = 3, y = 2
Output: Minimum distance between 3 and 2 is 1.
4. Find a peak element
Given an array of integers. Find a peak element in it. An array element is a peak if it is NOT smaller than its neighbours. For corner elements, we need to consider only one neighbour. (Solution)
Example:
Input: array[]= {5, 10, 20, 15}
Output: 20
Explanation: The element 20 has neighbours 10 and 15,
both of them are less than 20.
Input: array[] = {10, 20, 15, 2, 23, 90, 67}
Output: 20 or 90
Explanation: The element 20 has neighbours 10 and 15,
both of them are less than 20, similarly 90 has neighbous 23 and 6700.
5. Count Strictly Increasing Subarrays
Given an array of integers, count number of subarrays (of size more than one) that are strictly increasing.
Expected Time Complexity : O(n)
Expected Extra Space: O(1) (Solution)
Expected Time Complexity : O(n)
Expected Extra Space: O(1) (Solution)
Examples:
Input: arr[] = {1, 4, 3} Output: 1 There is only one subarray {1, 4}
Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2. (Solution)
Example:
7. Segregate 0s and 1s in an arrayInput: arr[] = {3, 1, 4, 6, 5}
Output: True
There is a Pythagorean triplet (3, 4, 5).
You are given an array of 0s and 1s in random order. Segregate 0s on left side and 1s on right side of the array. Traverse array only once. (Solution)
Input array = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]
Output array = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space. (Solution)
Example:
Input : n = 7 and array[] = {1, 2, 3, 1, 3, 6, 6}
Output: 1, 3, 6
Explanation: The numbers 1 , 3 and 6 appears more
than once in the array.
9. Two elements whose sum is closest to zero
An Array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero. (Solution)
10. Maximum Length Bitonic Subarray | (O(n) time and O(n) space)
Given an array A[0 … n-1] containing n positive integers, a subarray A[i … j] is bitonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] … = A[k + 1] >= .. A[j – 1] > = A[j]. Write a function that takes an array as argument and returns the length of the maximum length bitonic subarray.
Expected time complexity of the solution is O(n)
Expected time complexity of the solution is O(n)
Simple Examples
1) A[] = {12, 4, 78, 90, 45, 23}, the maximum length bitonic subarray is {4, 78, 90, 45, 23} which is of length 5. (Solution)
1) A[] = {12, 4, 78, 90, 45, 23}, the maximum length bitonic subarray is {4, 78, 90, 45, 23} which is of length 5. (Solution)
11. Find minimum number of merge operations to make an array palindrome
Given an array of positive integers. We need to make the given array a ‘Palindrome’. Only allowed operation on array is merge. Merging two adjacent elements means replacing them with their sum. The task is to find minimum number of merge operations required to make given array a ‘Palindrome’.
To make an array a palindromic we can simply apply merging operations n-1 times where n is the size of array (Note a single element array is alway palindrome similar to single character string). In that case, size of array will be reduced to 1. But in this problem we are asked to do it in minimum number of operations. (Solution)
Example :
Input : arr[] = {15, 4, 15}
Output : 0
Array is already a palindrome. So we
do not need any merge operation.
Input : arr[] = {1, 4, 5, 1}
Output : 1
We can make given array palindrome with
minimum one merging (merging 4 and 5 to
make 9)
Given a 2D array, print it in spiral form. See the following examples. (Solution)
Examples:
Input:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Given an array of distinct integers, find length of the longest subarray which contains numbers that can be arranged in a continuous sequence. (Solution)
Examples:
Input: arr[] = {10, 12, 11}; Output: Length of the longest contiguous subarray is 3
The cost of a stock on each day is given in an array, find the max profit that you can make by buying and selling in those days. For example, if the given array is {100, 180, 260, 310, 40, 535, 695}, the maximum profit can earned by buying on day 0, selling on day 3. Again buy on day 4 and sell on day 6. If the given array of prices is sorted in decreasing order, then profit cannot be earned at all. (Solution)
Post a Comment