Next Greater Element

Next Greater Element

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Solution:

1) Push the first element to stack.
2) Pick rest of the elements one by one and follow following steps in loop.
....a) Mark the current element as next.
....b) If stack is not empty, then pop an element from stack and compare it with next.
....c) If next is greater than the popped element, then next is the next greater element fot the popped element.
....d) Keep poppoing from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
....g) If next is smaller than the popped element, then push the popped element back.
3) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.

void printNGE(int arr[], int n)

{

int i = 0;

struct stack s;

s.top = -1;

int element, next;

/* push the first element to stack */

push(&s, arr[0]);

// iterate for rest of the elements

for (i=1; i

{

next = arr[i];

if (isEmpty(&s) == false)

{

// if stack is not empty, then pop an element from stack

element = pop(&s);

/* If the popped element is smaller than next, then

a) print the pair

b) keep popping while elements are smaller and

stack is not empty */

while (element < next)

{

printf("\n %d --> %d", element, next);

if(isEmpty(&s) == true)

break;

element = pop(&s);

}

/* If element is greater than next, then push

the element back */

if (element > next)

push(&s, element);

}

/* push next to stack so that we can find

next greater for it */

push(&s, next);

}

/* After iterating over the loop, the remaining

elements in stack do not have the next greater

element, so print -1 for them */

while(isEmpty(&s) == false)

{

element = pop(&s);

next = -1;

printf("\n %d --> %d", element, next);

}

}

A Boolean Matrix Question

A Boolean Matrix Question

Given a boolean matrix mat[M][N] of size M X N, modify it such that if a matrix cell mat[i][j] is 1 (or true) then make all the cells of ith row and jth column as 1.
if a[i][j]=1
then fill a[i][k]=1 where k 0 to N
and fill a[k][j]=1 where k 0 to M

Method 1 (Use two temporary arrays)
1) Create two temporary arrays row[M] and col[N]. Initialize all values of row[] and col[] as 0.
2) Traverse the input matrix mat[M][N]. If you see an entry mat[i][j] as true, then mark row[i] and col[j] as true.
3) Traverse the input matrix mat[M][N] again. For each entry mat[i][j], check the values of row[i] and col[j]. If any of the two values (row[i] or col[j]) is true, then mark mat[i][j] as true.

void modifyMatrix(bool mat[R][C])

{

bool row[R]={0};

bool col[C]={0};

int i, j;

/* Store the rows and columns to be marked as 1 in row[] and col[]

arrays respectively */

for (i = 0; i < R; i++)

{

for (j = 0; j < C; j++)

{

if (mat[i][j] == 1)

{

row[i] = 1;

col[j] = 1;

}

}

}

/* Modify the input matrix mat[] using the above constructed row[] and

col[] arrays */

for (i = 0; i < R; i++)

{

for (j = 0; j < C; j++)

{

if ( row[i] == 1 || col[j] == 1 )

{

mat[i][j] = 1;

}

}

}

}

Method 2 (A Space Optimized Version of Method 1)
This method is a space optimized version of above method 1. This method uses the first row and first column of the input matrix in place of the auxiliary arrays row[] and col[] of method 1. So what we do is: first take care of first row and column and store the info about these two in two flag variables rowFlag and colFlag. Once we have this info, we can use first row and first column as auxiliary arrays and apply method 1 for submatrix (matrix excluding first row and first column) of size (M-1)*(N-1).

1) Scan the first row and set a variable rowFlag to indicate whether we need to set all 1s in first row or not.
2) Scan the first column and set a variable colFlag to indicate whether we need to set all 1s in first column or not.
3) Use first row and first column as the auxiliary arrays row[] and col[] respectively, consider the matrix as submatrix starting from second row and second column and apply method 1.
4) Finally, using rowFlag and colFlag, update first row and first column if needed.

Time Complexity: O(M*N)
Auxiliary Space: O(1)

void modifyMatrix(bool mat[R][C])

{

bool rowFirst;

bool colFirst;

int i, j;

for (i = 0; i < C; i++)

{

if(mat[0][i]){ rowFirst=1; break;


}

for (i = 0; i < R; i++)

{

if(mat[i][o]) { colFirst=1 ; break;}


}

for (i = 1; i < R; i++)

{

for (j = 1; j < C; j++)

{

if (mat[i][j] == 1)

{

mat[i][0] = 1;

mat[0][j] = 1;

}

}

}

for (i = 1; i < R; i++)

{

for (j = 1; j < C; j++)

{

if ( mat[i][0] == 1 || mat[0][j] == 1 )

{

mat[i][j] = 1;

}

}

}

if(rowFirst)
for (i = 0; i < R; i++)
mat[0][i]=1;
if(colFirst)
for (i = 0; i < C; i++)
mat[i][0]=1;


}

* Find duplicates in O(n) time and O(1) extra space

/*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.*/

#include "stdio.h"

#include"stdlib.h"
void printRepeating(int arr[], int size)
{
int i,index=0;
printf("The repeating elements are: \n");
for(i = 0; i < size; i++)
{
index=abs(arr[i])%size;
if(arr[index] == 0)
arr[index]=-size;
else if(arr[index]>0 && arr[index]<size)
arr[index] = -arr[index];
else if(arr[index]<0)
{
printf(" %d ", abs(arr[i]));
arr[index]=-arr[index];
arr[index]+=size;
}
}
//restore previous array
for(i=0;i <size;i++)
arr[i]=abs(arr[i])%size;
}

int main()
{
int arr[] = {1, 1,1,1,1,1,2,2,3,0,0,0};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;
}

Write a C program to sort a stack in ascending order without using extra space

Write a C program to sort a stack in ascending order. You should not
make any assumptions about how the stack is implemented. The following
are the only
functions that should be used to write this program:
Push | Pop | Top | IsEmpty | IsFull
Method 1: Recursion

void sort(stack)
{
type x;

if (!isEmpty(stack)) {
x = pop(stack);
sort(stack);
insert(x, stack);
}
}

void insert(x, stack)
{
type y;

if (!isEmpty(stack) && top(stack) .<. x) y = pop(stack);
insert(x, stack);
push(y, stack);
} else {
push(x, stack);
}
}


Method:2 Iterative use one more stack
void sort_stack(Stack * src, Stack * dest)
{
while (!src->IsEmpty())
{
Int tmp = src->Pop();
while(!dest->IsEmpty() && dest->Top() > tmp)
{
src->Push(dest->Pop());
}
dest->Push(tmp);
}


Methode 3:
ascending(stack *s, int top){
IsEmpty(s){
push(top);
return;
}
i = pop(s);
if(i .<. top){
ascending(s, top);
push(i);
}
else{
ascending(s, i);
push(top);
}

}

What do lvalue and rvalue mean?

What do lvalue and rvalue mean?
An lvalue is an expression that could appear on the left-hand sign of an assignment (An object that has a location). An rvalue is any
expression that has a value (and that can appear on the right-hand sign of an assignment).
The lvalue refers to the left-hand side of an assignment expression. It must always evaluate to a memory location. The rvalue represents the
right-hand side of an assignment expression; it may have any meaningful combination of variables and constants.
Is an array an expression to which we can assign a value?
An lvalue was defined as an expression to which a value can be assigned. The answer to this question is no, because an array is composed
of several separate array elements that cannot be treated as a whole for assignment purposes.
The following statement is therefore illegal:
int x[5], y[5];
x = y;
Additionally, you might want to copy the whole array all at once. You can do so using a library function such as the memcpy() function, which
is shown here:
memcpy(x, y, sizeof(y));
It should be noted here that unlike arrays, structures can be treated as lvalues. Thus, you can assign one
structure variable to another structure variable of the same type, such as this:
typedef struct t_name
{
char last_name[25];
char first_name[15];
char middle_init[2];
} NAME;
...
NAME my_name, your_name;
...
your_name = my_name;

Whats wrong with the expression a[i]=i++; ? Whats a sequence point?

Whats wrong with the expression a[i]=i++; ? Whats a sequence point?
Although its surprising that an expression like i=i+1; is completely valid, something like a[i]=i++; is not. This is because all accesses to an
element must be to change the value of that variable. In the statement a[i]=i++; , the access to i is not for itself, but for a[i] and so its
invalid. On similar lines, i=i++; or i=++i; are invalid. If you want to increment the value of i, use i=i+1; or i+=1; or i++; or ++i; and not some
combination.
A sequence point is a state in time (just after the evaluation of a full expression, or at the ||, &&, ?:, or comma operators, or just before a
call to a function) at which there are no side effects.
The ANSI/ISO C Standard states that
Between the previous and next sequence point an object shall have its stored
value modified at most once by the evaluation of an expression. Furthermore,
the prior value shall be accessed only to determine the value to be stored.
At each sequence point, the side effects of all previous expressions will be completed. This is why you cannot rely on expressions such as
a[i] = i++;, because there is no sequence point specified for the assignment, increment or index operators, you don't know when the effect
of the increment on i occurs.
The sequence points laid down in the Standard are the following:

1.The point of calling a function, after evaluating its arguments.
2.The end of the first operand of the && operator.
3.The end of the first operand of the || operator.
4.The end of the first operand of the ?: conditional operator.
5.The end of the each operand of the comma operator.
6.Completing the evaluation of a full expression. They are the following:
1-Evaluating the initializer of an auto object.
2-The expression in an ?ordinary? statement?an expression followed by semicolon.
3-The controlling expressions in do, while, if, switch or for statements.
4-The other two expressions in a for statement.
5-The expression in a return statement.

Segmentation fault, access violation, core dump and Bus error

What do Segmentation fault, access violation, core dump and Bus error mean?
The segmentation fault, core dump, bus error kind of errors usually mean that the program tried to access memory it shouldn't have.
Probable causes are overflow of local arrays; improper use of null pointers; corruption of the malloc() data structures; mismatched function
arguments (specially variable argument functions like sprintf(), fprintf(), scanf(), printf()).
For example, the following code is a sure shot way of inviting a segmentation fault in your program:
sprintf(buffer,"%s %d","Hello");
So whats the difference between a bus error and a segmentation fault?
A bus error is a fatal failure in the execution of a machine language instruction resulting from the processor
detecting an anomalous condition on its bus.
Such conditions include:
-
-
-
-
-
Invalid address alignment (accessing a multi-byte number at an odd address).
Accessing a memory location outside its address space.
Accessing a physical address that does not correspond to any device.
Out-of-bounds array references.
References through uninitialized or mangled pointers.
A bus error triggers a processor-level exception, which Unix translates into a "SIGBUS" signal,which if not caught, will terminate the current
process. It looks like a SIGSEGV, but the difference between the two is that SIGSEGV indicates an invalid access to valid
memory, while SIGBUS indicates an access to an invalid address.
Bus errors mean different thing on different machines. On systems such as Sparcs a bus error occurs when you access memory that is not
positioned correctly.
Maybe an example will help to understand how a bus error occurs
#include " stdlib.h"
#include " stdio.h"
int main(void)
{
char *c;
long int *i;
c = (char *) malloc(sizeof(char));
c++;
i = (long int *)c;
printf("%ld", *i);
return 0;
}
On Sparc machines long ints have to be at addresses that are multiples of four (because they are four bytes long), while chars do not (they
are only one byte long so they can be put anywhere). The example code uses the char to create an invalid address, and assigns the long int
to the invalid address. This causes a bus error when the long int is dereferenced.
A segfault occurs when a process tries to access memory that it is not allowed to, such as the memory at address 0 (where NULL usually
points). It is easy to get a segfault, such as the following example, which dereferences NULL.
#include " stdio.h"
int main(void)
{
char *p;
p = NULL;
putchar(*p);
return 0;
}