Minimum element in diagonal strips of square matrix?

I need to find the minimum in each diagonal strip (perpendicular to main diagonal) for square matrix. The code I'm using, does in fact output each strip, but for some reason it doesn't find the min element.

#include<stdio.h>

int main(){
    int min[10], x[3][3] = { 1, 2, 3,
                             4, 5, 6,
                             7, 8, 9};
    int n = 3, d, j, z, i, k;

    for (d = 0, i = 0; d < 2 * n - 1; d++, i++){
        printf("D %d: ", d);
        z = (d < n) ? 0 : d - n + 1;
        for (j = z; j <= d - z; j++){
            printf("%d ", x[j][d - j]);
            if(d == 0 || d == 2 * n - 2){
                min[i] = x[j][d - j];
                break;
            }
            min[i] = x[j][d - j];
            for (k = j + 1; k <= d - z; k++){
                if (min[i] > x[k][d - k])
                    min[i] = x[k][d - k];
            }
        }
        printf("\n");
    }
    printf("\n");
    for (i = 0; i < 2 * n - 1; i++)
        printf("min = %d\n", min[i]);

    return 0;
}

Output:

D 0: 1
D 1: 2 4
D 2: 3 5 7
D 3: 6 8
D 4: 9
min = 1
min = 4
min = 7
min = 8
min = 9

But in this case it should be

min = 1
min = 2
min = 3
min = 6
min = 9

2 answers

  • answered 2018-05-16 06:22 4386427

    I think you make it more complicated than needed and I find it hard to understand what your algorithm is.

    I'll suggest that you simply calculates the minimum in the loop where you do the printing.

    Something like:

    #include<stdio.h>
    
    int main(){
        int min[10], x[3][3] = { {1, 2, 3},
                                 {4, 5, 6},
                                 {7, 8, 9}};
        int n = 3, d, j, z, i;
    
        for (d = 0, i = 0; d < 2 * n - 1; d++, i++){
            printf("D %d: ", d);
            z = (d < n) ? 0 : d - n + 1;
            for (j = z; j <= d - z; j++){
                printf("%d ", x[j][d - j]);
                if (j == z)
                {
                  // First time for this strip
                  // So just initialize min to current element
                  min[d] = x[j][d - j];
                }
                else if (min[d] > x[j][d - j])
                {
                  // Current element is less than min
                  // So overwrite min with current element
                  min[d] = x[j][d - j];
                }
                if(d == 0 || d == 2 * n - 2){
                    break;
                }
            }
            printf("\n");
        }
        printf("\n");
        for (i = 0; i < 2 * n - 1; i++)
            printf("min = %d\n", min[i]);
    
        return 0;
    }
    

  • answered 2018-05-16 06:54 Jonathan Leffler

    I think you can control the loops with fewer special conditions. The main trouble in the original loop was that you had triple nested loops where double nested loops are sufficient. This meant you kept on setting the min to a new value too often.

    This code prints out the subscripts of the elements of the array as well as the value.

    #include <stdio.h>
    
    int main(void)
    {
        int min[10], x[3][3] =
        {
            { 1, 2, 3, },
            { 4, 5, 6, },
            { 7, 8, 9, },
        };
        int n = 3;
    
        for (int d = 0; d < 2 * n - 1; d++)
        {
            printf("D %d: ", d);
            int z = (d < n) ? 0 : d - n + 1;
            printf("A[%d][%d] = %d: ", z, d - z, x[z][d - z]);
            min[d] = x[z][d - z];
            for (int j = z + 1; j <= d - z; j++)
            {
                printf("A[%d][%d] = %d: ", j, d - j, x[j][d - j]);
                if (x[j][d-j] < min[d])
                    min[d] = x[j][d-j];
            }
            printf("min[%d] = %d\n", d, min[d]);
        }
    
        printf("\n");
    
        for (int i = 0; i < 2 * n - 1; i++)
            printf("min = %d\n", min[i]);
    
        return 0;
    }
    

    Output:

    D 0: A[0][0] = 1: min[0] = 1
    D 1: A[0][1] = 2: A[1][0] = 4: min[1] = 2
    D 2: A[0][2] = 3: A[1][1] = 5: A[2][0] = 7: min[2] = 3
    D 3: A[1][2] = 6: A[2][1] = 8: min[3] = 6
    D 4: A[2][2] = 9: min[4] = 9
    
    min = 1
    min = 2
    min = 3
    min = 6
    min = 9